iterator - 逐步完成所有排列，一次交换

Question

给定一个由n个不同项组成的列表，我如何逐步检查这些项的每个排列，一次只交换一对值？ (我认为这是有可能的，当然感觉应该是。)

我正在寻找的是一个迭代器，该迭代器产生要交换的下一对项的索引，这样，如果迭代n!-1次，它将逐步遍历n!。以某种顺序排列列表。如果再次对其进行迭代，则可以将列表恢复为其开始顺序，这将是一个奖励，但这不是必须的。如果所有对都将第一个(分别是最后一个)元素作为对中的一个，则该函数仅需要返回一个值，这也将是一个奖励。

示例:-对于3个元素，您可以将最后一个元素与第一个元素和第二个元素交替交换以遍历排列，即:(abc)swap 0-2 =>(cba)1-2(cab)0-2( bac)1-2(bca)0-2(acb)。

我将用C来实现，但可能会困惑大多数语言的解决方案。

Answer 1

我确定对您来说太迟了，但是我发现这个问题很不错:Steinhaus–Johnson–Trotter algorithm及其变体完全可以满足您的要求。此外，它还具有始终交换相邻索引的附加属性。我试图将Java中的一种变体(偶数)实现为迭代器，并且效果很好:

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();
    }
}

很容易将其修改为无限迭代器，该迭代器将在最后重新启动循环，或者将其返回返回交换索引而不是下一个排列的迭代器。

Here收集各种实现的另一个链接。