Given a list of n distinct items, how can I step through each permutation of the items swapping just one pair of values at a time? (I assume it is possible, it certainly feels like it should be.)
What I'm looking for is an iterator that yields the indices of the next pair of items to swap, such that if iterated n!-1 times it will step through the n! permutations of the list in some order. If iterating it once more would restore the list to its starting order that would be a bonus, but it isn't a requirement. If all pairs involve the first (resp. the last) element as one of the pair, so that the function only needs to return a single value, that would also be a bonus.
Example:- for 3 elements, you can swap the last element alternately with the first and second elements to loop through the permutations, viz: (a b c) swap 0-2 => (c b a) 1-2 (c a b) 0-2 (b a c) 1-2 (b c a) 0-2 (a c b).
I'll be implementing in C, but can probably puzzle out solutions in most languages.
How do you go through all permutations?
There is a way of counting from 0 to (n! - 1) that will list off all permutations of a list of n elements. The idea is to rewrite the numbers as you go using the factorial number system and interpreting the number as an encoded way of determining which permutation to use.
How does the Johnson Trotter algorithm work?
The Steinhaus–Johnson–Trotter algorithm follows this structure: the sequence of permutations it generates consists of. in the first block are in descending order, in the second block they are in ascending order, in the third block they are in descending order, and so on.
How does Heap's algorithm work?
Heap's algorithm is used to generate all permutations of n objects. The idea is to generate each permutation from the previous permutation by choosing a pair of elements to interchange, without disturbing the other n-2 elements. Following is the illustration of generating all the permutations of n given numbers.
How do you generate all permutations of an array?
You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element.
I'm sure it's too late for you, but I found a nice addition to this question: Steinhaus–Johnson–Trotter algorithm and its variants do exactly what you asked for. Moreover it has the additional property that it always swaps adjacent indices. I tried to implement one of the variants (Even's) in Java as an iterator and works nicely:
import java.util.*;// Based on https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm#Even.27s_speeduppublic class PermIterator implements Iterator<int[]>{ private int[] next = null; private final int n; private int[] perm; private int[] dirs; public PermIterator(int size) { n = size; if (n <= 0) { perm = (dirs = null); } else { perm = new int[n]; dirs = new int[n]; for(int i = 0; i < n; i++) { perm[i] = i; dirs[i] = -1; } dirs[0] = 0; } next = perm; } @Override public int[] next() { int[] r = makeNext(); next = null; return r; } @Override public boolean hasNext() { return (makeNext() != null); } @Override public void remove() { throw new UnsupportedOperationException(); } private int[] makeNext() { if (next != null) return next; if (perm == null) return null; // find the largest element with != 0 direction int i = -1, e = -1; for(int j = 0; j < n; j++) if ((dirs[j] != 0) && (perm[j] > e)) { e = perm[j]; i = j; } if (i == -1) // no such element -> no more premutations return (next = (perm = (dirs = null))); // no more permutations // swap with the element in its direction int k = i + dirs[i]; swap(i, k, dirs); swap(i, k, perm); // if it's at the start/end or the next element in the direction // is greater, reset its direction. if ((k == 0) || (k == n-1) || (perm[k + dirs[k]] > e)) dirs[k] = 0; // set directions to all greater elements for(int j = 0; j < n; j++) if (perm[j] > e) dirs[j] = (j < k) ? +1 : -1; return (next = perm); } protected static void swap(int i, int j, int[] arr) { int v = arr[i]; arr[i] = arr[j]; arr[j] = v; } // ----------------------------------------------------------------- // Testing code: public static void main(String argv[]) { String s = argv[0]; for(Iterator<int[]> it = new PermIterator(s.length()); it.hasNext(); ) { print(s, it.next()); } } protected static void print(String s, int[] perm) { for(int j = 0; j < perm.length; j++) System.out.print(s.charAt(perm[j])); System.out.println(); }}It'd be easy to modify it to an infinite iterator that restarts the cycle at the end, or an iterator that would return the swapped indices instead of the next permutation.
Here another link collecting various implementations.
Ah, once I calculated a sequence for n=4 (with the "always swap the first item with another" constraint), I was able to find sequence A123400 in the OEIS, which told me I need "Ehrlich's swap method".
Google found me a C++ implementation, which I assume from this is under the GPL. I've also found Knuth's fascicle 2b which describes various solutions to exactly my problem.
Once I have a tested C implementation I'll update this with code.
Here's some perl code that implements Ehrlich's method based on Knuth's description. For lists up to 10 items, I tested in each case that it correctly generated the complete list of permutations and then stopped.
## Given a count of items in a list, returns an iterator that yields the index# of the item with which the zeroth item should be swapped to generate a new# permutation. Returns undef when all permutations have been generated.## Assumes all items are distinct; requires a positive integer for the count.#sub perm_iterator { my $n = shift; my @b = (0 .. $n - 1); my @c = (undef, (0) x $n); my $k; return sub { $k = 1; $c[$k++] = 0 while $c[$k] == $k; return undef if $k == $n; ++$c[$k]; @b[1 .. $k - 1] = reverse @b[1 .. $k - 1]; return $b[$k]; };}Example use:
#!/usr/bin/perl -wuse strict;my @items = @ARGV;my $iterator = perm_iterator(scalar @items);print "Starting permutation: @items\n";while (my $swap = $iterator->()) { @items[0, $swap] = @items[$swap, 0]; print "Next permutation: @items\n";}print "All permutations traversed.\n";exit 0;By request, python code. (Sorry, it probably isn't overly idiomatic. Suggestions for improvement welcomed.)
class ehrlich_iter: def __init__(self, n): self.n = n self.b = range(0, n) self.c = [0] * (n + 1) def __iter__(self): return self def next(self): k = 1 while self.c[k] == k: self.c[k] = 0 k += 1 if k == self.n: raise StopIteration self.c[k] += 1 self.b[1:k - 1].reverse return self.b[k]mylist = [ 1, 2, 3, 4 ] # test itprint "Starting permutation: ", mylistfor v in ehrlich_iter(len(mylist)): mylist[0], mylist[v] = mylist[v], mylist[0] print "Next permutation: ", mylistprint "All permutations traversed."