mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-11-24, 07:13   #1
sticky
 
Nov 2020

2 Posts
Default Number with all permutations between any 2 digits

Lets say you are given a set of n consecutive digits , Ex {0,1,2,3}. You are required to form a number using the digits which abides by the following rule:

1.The number should cover all relations (ex 12 and 21) between any 2 digits from the set of numbers

For the given set this number would be :0123130203210 or 0123021310320.

I was able to get this number manually by trial and error. Is there a deterministic way of achieving this number for any n consecutive digits?

The number will have all the 2 digit permutations only once.

0 -> [1,2,3] will yield 01 , 02 , 03
1 -> [0,2,3] will yield 10 , 12 , 13
2 -> [0,1,3] will yield 20 , 21 , 23
3 -> [0,1,2] will yield 30 , 31 , 32
We have to generate a number which will cover all the above relations.

Last fiddled with by sticky on 2020-11-24 at 08:04
sticky is offline   Reply With Quote
Old 2020-11-24, 10:14   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52·7·53 Posts
Default

Why can't you just list all C(n,2) in a row lexicografic and add a zero at the end?
0102031213230
This is deterministic and correct (can you prove?).
LaurV is offline   Reply With Quote
Old 2020-11-24, 13:24   #3
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

6038 Posts
Default

I think what you are looking for is the Superpermutation page on Wikipedia.
Viliam Furik is offline   Reply With Quote
Old 2020-11-24, 13:44   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·5·7·31 Posts
Default

1) It occurred to me to wonder whether this might be a homework problem.

2) IMO this is not "superpermutations." For the problem as described, the the "list all transpositions" approach seems to be appropriate.

A concept related, but not directly related to this problem, is that of a transitive group.
Dr Sardonicus is offline   Reply With Quote
Old 2020-11-24, 17:12   #5
sticky
 
Nov 2020

2 Posts
Default

The answer is Eulerian path.
Algorithm is Hierholzers path detection.
sticky is offline   Reply With Quote
Old 2020-11-24, 17:21   #6
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

32×43 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
2) IMO this is not "superpermutations."
Yes, but it's something like generalized superpermutations, with generalization being the fact that they consist of permutations of combinations of the symbols. So kind of like "Combinational superpermutations".

The example, 0123021310320, contains every permutation of every two-element combination of the 4 elements - {0;1;2;3}.
Viliam Furik is offline   Reply With Quote
Old 2020-11-25, 03:58   #7
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

22·167 Posts
Default

I didn't quite understand the question,
but I believe the Alternating group is relevant.

Briefly it is the set of all even number of transpositions.

see Wikipedia Alternating group.

Regards,
Matt
MattcAnderson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
number of digits enzocreti enzocreti 1 2020-01-16 18:23
who can factor this 128 digits number? aaa120 Factoring 19 2010-09-04 09:16
Number of digits display grobie 15k Search 13 2005-09-29 21:57
Number of n-element permutations with exactly k inversions tytus Math 3 2005-02-04 10:10
how do you find number of digits of a 2^n number? Unregistered Math 11 2004-11-30 22:53

All times are UTC. The time now is 07:21.

Fri Mar 5 07:21:44 UTC 2021 up 92 days, 3:33, 0 users, load averages: 1.39, 1.47, 1.41

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.