繰り返し要素を含む配列のすべての順列を生成するにはどうすればよいですか?

配列のすべての順列の生成

個別の要素の配列が与えられた場合、目的は、配列要素の考えられるすべての順列をリストすることです。

アルゴリズム

次のアルゴリズムは、O(N!) 時間ですべての順列を生成します。複雑さ:

1. 初期化: i = 0 を設定します。
2. 配列の反復: i が配列の長さより小さい間:
3. Swap: インデックス i の要素をそれぞれと交換します配列内の残りの要素。
4. Recurse: 新しい i 値として i 1 を使用してアルゴリズムを再帰的に呼び出します。
5. スワップ バック:再帰呼び出しの後、要素を元の要素に戻します。位置。
6. i をインクリメント: i を 1 ずつインクリメントします。

Python 実装

def permute(arr, i=0):
    if i == len(arr) - 1:
        print(arr)
        return

    for j in range(i, len(arr)):
        arr[i], arr[j] = arr[j], arr[i]
        permute(arr, i + 1)
        arr[i], arr[j] = arr[j], arr[i]

Jarvis March アルゴリズム

要素が繰り返される配列の場合、Jarvis March アルゴリズムはより優れたものです。効率的なアプローチ:

1. 並べ替え: 配列を昇順に並べ替えます。
2. 実行中: 完了していない間:
3. Find pivot: 要素がその要素よりも小さい最大のインデックスを見つけます後継者。
4. 隣接の検索: ピボット インデックスの要素より大きい、並べ替えられた部分の最後の要素を検索します。
5. 交換:ピボットと隣接する要素を交換しますindices.
6. Reverse: ピボット インデックスからソートされた部分の末尾までの要素を反転します。
7. Checkned: 配列が正しいかどうかを確認します。降順にソートされます。その場合は、ループを終了します。

Python 実装

def permute_repeated(arr):
    ind = [0] * len(arr)
    for i in range(len(arr)):
        ind[i] = i

    while True:
        yield [arr[i] for i in ind]

        for i in range(len(arr) - 2, -1, -1):
            if ind[i] < ind[i + 1]:
                break

        if i == -1:
            return

        for j in range(len(arr) - 1, -1, -1):
            if arr[j] > arr[i]:
                ind[i], ind[j] = ind[j], ind[i]
                break

        ind[i + 1:] = sorted(ind[i + 1:])

以上が繰り返し要素を含む配列のすべての順列を生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。