個別要素と非個別要素の両方を処理して、配列の可能なすべての順列を生成するにはどうすればよいでしょうか?

配列の置換

配列の置換の生成は、一般的な計算タスクです。個別の要素の配列が与えられた場合、これらの要素の可能な配置をすべて計算するにはどうすればよいでしょうか?

再帰アルゴリズム

順列生成の古典的なアルゴリズムの 1 つは再帰を使用します。中心となるアイデアは、配列内の各要素を潜在的な最初の要素とみなして、残りの要素を再帰的に並べ替えて、その最初の要素から始まるすべての可能な組み合わせを見つけることです。

// Recursive method for permutation generation
public static void permute(int[] arr, int k) {
    for (int i = k; i < arr.length; i++) {
        // Swap elements at positions k and i
        Collections.swap(arr, k, i);
        // Recursively permute the remaining elements
        permute(arr, k + 1);
        // Restore original order of elements
        Collections.swap(arr, k, i);
    }
    if (k == arr.length - 1) {
        // Once all elements are permuted, print the current permutation
        System.out.println(Arrays.toString(arr));
    }
}

このアルゴリズムでは、パラメーター k配列内の現在位置を追跡します。最初は、k は最初の要素を示す 0 に設定されます。位置 k ごとに、残りの要素を反復処理し、位置 k の要素と交換し、位置 k 1 から始まる配列の残りの部分を再帰的に並べ替えます。これにより、各要素から始まるすべての可能な配置が効果的に考慮されます。

個別要素の非再帰アルゴリズム

代替案、非再帰アルゴリズムは、配列内のすべての要素が個別である場合にうまく機能します。要素を繰り返し交換して順列を構築し、特定のパターンを実現します。

for (int tail = arr.length - 1; tail > 0; tail--) {
    // Find the first decreasing element from the end
    if (arr[tail - 1] < arr[tail]) {
        // Find the last element greater than the decreasing element
        int s = arr.length - 1;
        while (arr[tail - 1] >= arr[s]) {
            s--;
        }
        // Swap the decreasing element with the greater element
        swap(arr, tail - 1, s);
        // Reverse the order of elements after the swap
        reverse(arr, tail);
        break;
    }
}

このアルゴリズムは、配列内の要素の昇順シーケンスから始まります。配列を右から左にスキャンして、最初に減少する要素を探します。減少する要素を見つけると、それを配列の末尾にある、それより大きい最小の要素と交換します。最後に、末尾の要素の順序を逆にして、次の順列を取得します。

同じ要素に対する非再帰アルゴリズム

配列内の要素が異なる場合HashMap を使用して要素をインデックスにマップすることで、潜在的な可能性を処理できます。繰り返し:

// Create a HashMap to map elements to their indices
Map<E, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
    map.put(arr[i], i);
}
// Sort the array in ascending order
Arrays.sort(arr);
// Initialize the index array
int[] ind = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
    ind[i] = map.get(arr[i]);
}

適切なマッピングとインデックス付けを使用すると、同じ非再帰アルゴリズムですべての順列を生成し、繰り返される要素を適切に処理できます。

以上が個別要素と非個別要素の両方を処理して、配列の可能なすべての順列を生成するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。