Transposal generators like {1, 1, 2, 3, 3, 2}

Question

The sequence {1, 1, 2, 3, 3, 2} generates all the transposals of {1,2,3}. Just cyclically pick positions $n, n+2, n+4$.

Is there a sequence like this for 1-4, 1-5, and so on?

Answer 1

Yes, it is always possible for any $N$. Here's how to make such a list with $N=4$ for example.

(1) You make a list of all permutations of [1,2,3,4] : for example, 1234, 1243, 1432, 4123, 4321, ..., and so on. There will be $N!$ such permutations.

(2) Once you have made a list of all permutations, you want to make a smaller list containing just a few selected permutations. In particular, you want to make a list where none of the members is a cyclic permutation of any other member.

Here's how you can do it: start with your complete list of permutations. Circle the first element, and cross out every cyclic permutation of it in the list. Then find the next element that isn't crossed out. Circle it, and cross out every cyclic permutation of it from the list. Repeat this process until you've either crossed out or circled each element. The circled elements will be your smaller list.

When I do this procedure, I end up with the following permutations (you might have a different set):

[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]

In general, cyclic permutations of the numbers $1...N$ come in groups of size $N$. Because there were $N!$ permutations originally and you've picked one permutation from each group, your smaller list will always have $(N-1)!$ elements in it.

(3) I'll arrange the permutations in a matrix like this: $$\begin{bmatrix}1&2&3&4\\1&2&4&3\\1&3&2&4\\1&3&4&2\\1&4&2&3\\1&4&3&2\\\end{bmatrix}$$

(4) Now if you read down the columns of the matrix, you'll get just the list you want:

$$[1,1,1,1,1,1,\;\; 2,2,3,3,4,4,\;\;3,4,2,4,2,3,\;\;4,3,4,2,3,2]$$

Just start at any point, reading every 6th entry, to get the $N$ permutations of $1\ldots N$. (In general, you'll read every $(N-1)!$ entry.)

Why does this work? If you pick a starting position where you don't "wrap around", you'll get one of the permutations from your shorter list. If you pick a starting position where you do wrap around, you'll get a cyclic permutation of a permutation in your shorter list.

We made sure that every permutation is either a member of the shorter list, or is a cyclic permutation of a member of the shorter list — so we've exhaustively covered all of the possible permutations.

---

Here is a generator for $N=5$, which I made using the same procedure. (Here, you'll take every $4!=24$th element.)

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5 , 5, 5, 5, 3, 3, 4, 4, 5, 5, 2, 2, 4, 4, 5, 5, 2, 2, 3, 3, 5, 5, 2, 2, 3, 3, 4, 4, 4, 5, 3, 5, 3, 4, 4, 5, 2, 5, 2, 4, 3, 5, 2, 5, 2, 3, 3, 4, 2, 4, 2, 3, 5, 4, 5, 3, 4, 3, 5, 4, 5, 2, 4, 2, 5, 3, 5, 2, 3, 2, 4, 3, 4, 2, 3, 2]

---

I hope this helps! Let me know if you have any questions.