iterator - 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

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_speedup
public 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.