Stepping through all permutations one swap at a time

Question

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.

Answer 1

Have a look at the C++ standard library function next_permuation(...). That should be a good starting point.

Answer 2

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 -w
use 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 it
print "Starting permutation: ", mylist
for v in ehrlich_iter(len(mylist)):
  mylist[0], mylist[v] = mylist[v], mylist[0]
  print "Next permutation: ", mylist
print "All permutations traversed."