Number with all permutations between any 2 digits

sticky · 2020-11-24, 07:13

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.

LaurV · 2020-11-24, 10:14

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?).

Viliam Furik · 2020-11-24, 13:24

I think what you are looking for is the Superpermutation page on Wikipedia.

Dr Sardonicus · 2020-11-24, 13:44

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.

sticky · 2020-11-24, 17:12

The answer is Eulerian path.
Algorithm is Hierholzers path detection.

Viliam Furik · 2020-11-24, 17:21

Quote:

Originally Posted by Dr Sardonicus

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}.

MattcAnderson · 2020-11-25, 03:58

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

2020-11-24, 07:13	#1
sticky Nov 2020 2² Posts	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

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

2020-11-24, 10:14	#2
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 3·23·149 Posts	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?).

2020-11-24, 13:24	#3
Viliam Furik "Viliam Furík" Jul 2018 Martin, Slovakia 319₁₆ Posts	I think what you are looking for is the Superpermutation page on Wikipedia.

2020-11-24, 13:44	#4
Dr Sardonicus Feb 2017 Nowhere 6,229 Posts	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.

2020-11-24, 17:12	#5
sticky Nov 2020 4₁₀ Posts	The answer is Eulerian path. Algorithm is Hierholzers path detection.

2020-11-25, 03:58	#7
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 2³·149 Posts	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