Generate colored permutations

Generate all colored permutations of the set $\{1,2,\ldots,n\}$ with $c$ colors. For $c=2$ colors these are also known as signed permutations.
Algorithm
Size $n$ of ground set (max. 20)
Number $c$ of colors
Output format
Output  numbering graphics

Object info

A signed permutation of an $n$-element set of objects is a linear ordering of those objects where each element carries a sign $+$ or $-$. For example, the signed permutations of $\{1,2\}$ are $12,21,\bar{2}1,1\bar{2},\bar{1}\bar{2},\bar{2}\bar{1},2\bar{1},\bar{1}2$, where we conveniently denote an entry $i$ with a negative sign as $\bar{i}$. The algorithm generating signed permutations running on this website is a straightforward generalization of the Steinhaus-Johnson-Trotter algorithm for generating (unsigned) permutations. It is a cyclic Gray code that in each step either applies an adjacent transposition, preserving the signs, or changes the sign of the first entry, and it runs in time $O(1)$ per permutation (=loopless).

A generalization of the concept of signed permutations is that of colored permutations. Specifically, a colored permutation is a permutation where each entry is assigned one of $c$ colors. Note that the case of $c=2$ colors is equivalent to signed permutations. A listing of all colored permutations of $\{1,2,3\}$ with $c=3$ colors (black, red, blue) is shown below (read top to bottom, left to right):

The above listing does not use adjacent transpositions, but instead prefix reversals, where each color in the reversed prefix is incremented by 1 (modulo $c$). To the right of the permutation listing is the length of the prefix reversal required to go from one permutation to the next.

When $c=2$ (signed permutations), we can think of the permutations as a stack of "burnt pancakes" (each pancake is burnt on one side), so a prefix reversal of length $k$ corresponds to flipping the top $k$ pancakes in the stack. For example, the image below illustrates how a stack of 3 pancakes with burnt side up can be sorted so the pancakes are stacked smallest to largest (starting at the top) with burnt side down.

When $c=1$ and $c=2$, both a greedy minimum-flip and maximum-flip strategy will exhaustively list all colored permutations. The same listing can be achieved more efficiently with either recursive or iterative rules by studying the corresponding flip sequence. When $c>2$, the maximum-flip strategy no longer works; however, the minimum-flip strategy will still produce an exhaustive listing of colored permutations with a well-behaved flip sequence (as illustrated above for $n=3$ and $c=3$). The average flip length is constant. The algorithms used above (and available for download below) generate colored permutations in $O(1)$-amortized time per permutation. The listings also enjoy simple and efficient ranking and unranking algorithms which are available in the source code below. Details for the algorithms can be found in [CSW21, SW16a, SW16b, Zak84].

In the textual output of our algorithms, a colored permutation is printed as list of pairs, where the first entries are the values of the permutation, and the second entries are the colors. For signed permutations ($c=2$), the signs $+$ and $-$ are interpreted as the colors 1 and 2, respectively. For example, the signed permutation $(3,2,\bar{4},1)$ and the permutation (3,2,4,1) colored (1,1,2,1) are both printed as 3 1 | 2 1 | 4 2 | 1 1.

Enumeration (OEIS)

The number of permutations of an $n$-element set with $c$ colors is $c^nn!$.

Download source code

[C/C++ source code (GNU GPL)]

References