Javaでの配列の順列

1. 前書き

この記事では、配列の順列を作成する方法を見ていきます。
まず、順列とは何かを定義します。 次に、いくつかの制約を見ていきます。 そして3番目に、*それらを計算する3つの方法を見ます:再帰的に、反復的に、そしてランダムに。*
Javaでの実装に焦点を当てるので、数学的な詳細については詳しく説明しません。

2. 順列とは何ですか?

セットの順列は、要素の再配置です。 _n_個の要素で構成されるセットには、_n!_順列があります。 ここで、_n!_は階乗であり、_n_以下のすべての正の整数の積です。

2.1. 例

整数の配列[3,4,7]には、3つの要素と6つの順列があります。
n!  = 3!  = 1 x 2 x 3 = 6
順列:[3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. 制約

順列の数は、_n_で急速に増加します。 10個の要素のすべての順列を生成するには数秒しかかかりませんが、15個の要素のすべての順列を生成するには2週間かかります。
link:/uploads/Screenshot-2018-12-30-at-09.40.23-e1546159288775-100x44.png%20100w []

3. アルゴリズム

3.1. 再帰アルゴリズム

最初に見るアルゴリズムはhttps://en.wikipedia.org/wiki/Heap%27s_algorithm [ヒープのアルゴリズム]です。 *これは、反復ごとに1つの要素を交換することにより、すべての順列を生成する再帰アルゴリズムです。*
入力配列が変更されます。 必要ない場合は、メソッドを呼び出す前に配列のコピーを作成する必要があります。
public static <T> void printAllRecursive(
  int n, T[] elements, char delimiter) {

    if(n == 1) {
        printArray(elements, delimiter);
    } else {
        for(int i = 0; i < n-1; i++) {
            printAllRecursive(n - 1, elements, delimiter);
            if(n % 2 == 0) {
                swap(elements, i, n-1);
            } else {
                swap(elements, 0, n-1);
            }
        }
        printAllRecursive(n - 1, elements, delimiter);
    }
}
このメソッドは、2つのヘルパーメソッドを使用します。
private void swap(T[] input, int a, int b) {
    T tmp = input[a];
    input[a] = input[b];
    input[b] = tmp;
}
private void printArray(T[] input) {
    System.out.print('\n');
    for(int i = 0; i < input.length; i++) {
        System.out.print(input[i]);
    }
}
ここでは、結果を_System.out_に書き込みますが、結果を配列またはリストに簡単に保存できます。

3.2. 反復アルゴリズム

*ヒープのアルゴリズムは、反復を使用して実装することもできます:*
int[] indexes = new int[n];
int[] indexes = new int[n];
for (int i = 0; i < n; i++) {
    indexes[i] = 0;
}

printArray(elements, delimiter);

int i = 0;
while (i < n) {
    if (indexes[i] < i) {
        swap(elements, i % 2 == 0 ?  0: indexes[i], i);
        printArray(elements, delimiter);
        indexes[i]++;
        i = 0;
    }
    else {
        indexes[i] = 0;
        i++;
    }
}

3.3. 辞書編集順序の順列

要素が比較可能である場合、要素の自然順序でソートされた順列を生成できます:
public static <T extends Comparable<T>> void printAllOrdered(
  T[] elements, char delimiter) {

    Arrays.sort(elements);
    boolean hasNext = true;

    while(hasNext) {
        printArray(elements, delimiter);
        int k = 0, l = 0;
        hasNext = false;
        for (int i = elements.length - 1; i > 0; i--) {
            if (elements[i].compareTo(elements[i - 1]) > 0) {
                k = i - 1;
                hasNext = true;
                break;
            }
        }

        for (int i = elements.length - 1; i > k; i--) {
            if (elements[i].compareTo(elements[k]) > 0) {
                l = i;
                break;
            }
        }

        swap(elements, k, l);
        Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length));
    }
}
このアルゴリズムは、すべての反復で_reverse_操作を行うため、ヒープのアルゴリズムよりも配列の効率が低下します。

3.4. ランダム化アルゴリズム

_n_が大きい場合、配列をシャッフルすることにより、ランダムな順列を生成できます。
Collections.shuffle(Arrays.asList(elements));
これを数回実行して、順列のサンプルを生成できます。
同じ順列を複数回作成する場合がありますが、_n_の値が大きい場合、同じ順列を2回生成する可能性は低くなります。

4. 結論

配列のすべての順列を生成する方法はたくさんあります。 この記事では、再帰的および反復的なヒープのアルゴリズムと、並べ替えられた順列のリストを生成する方法について説明しました。
大きな配列に対してすべての順列を生成することは不可能なので、代わりにランダムな順列を生成できます。
この記事のすべてのコードスニペットの実装は、https://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-4 [Githubリポジトリ]にあります。