mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Number with all permutations between any 2 digits (https://www.mersenneforum.org/showthread.php?t=26223)

sticky 2020-11-24 07:13

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.

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 [URL="https://en.wikipedia.org/wiki/Superpermutation"]Superpermutation[/URL] 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 [i]not[/i] "superpermutations." For the problem as described, the the "list all transpositions" approach seems to be appropriate.

A concept related, but not [i]directly[/i] related to this problem, is that of a [i]transitive[/i] 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=Dr Sardonicus;564201]2) IMO this is [i]not[/i] "superpermutations."[/QUOTE]

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 [URL="https://en.wikipedia.org/wiki/Alternating_group"]Wikipedia Alternating group[/URL].

Regards,
Matt


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

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