10

n個の個別のアイテムのリストが与えられた場合、一度に値のペアを1つずつ交換して、アイテムの各順列をどのようにステップスルーできますか? （私はそれが可能だと思います、確かにそうあるべきだと感じています。）

私が探しているのは、スワップするアイテムの次のペアのインデックスを生成する反復子です。これにより、n!-1 回反復すると n! ある順序でのリストの順列。もう一度繰り返すと、リストが最初の順序に復元される場合はボーナスになりますが、必須ではありません。すべてのペアが最初の (それぞれ最後の) 要素をペアの 1 つとして含む場合、関数は 1 つの値のみを返す必要があるため、それもボーナスになります。

例:- 3 つの要素の場合、最後の要素を最初と 2 番目の要素と交互に交換して順列をループできます。つまり、 (abc) swap 0-2 => (cba) 1-2 (cab) 0-2 ( bac) 1-2 (bca) 0-2 (acb)。

私は C で実装しますが、おそらくほとんどの言語で解決策を見つけることができます。

4

4 に答える 4

18

遅すぎると思いますが、この質問に素晴らしい追加を見つけました.Steinhaus–Johnson–Trotterアルゴリズムとその変種は、まさにあなたが求めたことを行います. さらに、隣接するインデックスを常に交換するという追加のプロパティがあります。Java でイテレータとしてバリアント (Even の) の 1 つを実装しようとしましたが、うまく動作します。 

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

最後にサイクルを再開する無限反復子、または次の順列の代わりにスワップされたインデックスを返す反復子に変更するのは簡単です。

さまざまな実装を収集する別のリンクを次に示します。

于 2012-08-11T19:18:30.303 に答える
0

https://sourceforge.net/projects/swappermutation/を見ることができます。これはまさに要件の Java 実装であり、スワップを生成するイテレーターです。これは少し前に作成され、最近更新されました。

于 2013-10-13T20:41:29.443 に答える
0

C++ 標準ライブラリ関数 next_permuation(...) を見てください。それは良い出発点になるはずです。

于 2010-01-04T15:06:37.353 に答える