1

すべての可能なサイズのすべての順列を取得する関数を PHP で作成しようとしています。例は、開始するのに最適な方法だと思います。

$my_array = array(1,1,2,3);

さまざまなサイズの可能な順列:

1
1 // * 注を参照
2
3
1,1
1,2
1,3
// など、サイズ 2 のすべてのセットについて
1,1,2
1,1,3
1,2,1
// など、サイズ 3 のすべてのセットについて
1,1,2,3
1,1,3,2
// など、サイズ 4 のすべてのセットについて

注：重複があるかどうかは気にしません。この例では、将来の重複はすべて省略されています。

私がこれまでにPHPで持っているもの:

function getPermutations($my_array){

$permutation_length = 1;
$keep_going = true;    

while($keep_going){
    while($there_are_still_permutations_with_this_length){
        // Generate the next permutation and return it into an array
        // Of course, the actual important part of the code is what I'm having trouble with.
    }
    $permutation_length++;
    if($permutation_length>count($my_array)){
        $keep_going = false;
    }
    else{
        $keep_going = true;
        }
}

return $return_array;

}

私が考えることができる最も近いことは、配列をシャッフルし、最初の n 要素を選択し、それがすでに結果配列にあるかどうかを確認し、そうでない場合は追加し、数学的にその長さの可能な順列がなくなったときに停止することです. しかし、それは醜く、リソースの効率が悪いです。

疑似コードアルゴリズムは大歓迎です。

また、非常に大きな (価値のない) ボーナス ポイントの場合、関数で順列を 1 つだけ取得する方法はありますが、次の順列を取得するために以前のすべての順列を再計算する必要はありませんか?

たとえば、パラメーター 3 を渡します。これは、既に 3 つの順列が行われていることを意味し、前の 3 つをやり直さずに 4 を生成するだけですか? (パラメーターを渡す必要はありません。グローバルまたは静的に追跡できます)。

これを尋ねる理由は、配列が大きくなるにつれて、可能な組み合わせの数も増えるからです。要素が 12 個しかない 1 つの小さなデータ セットが急速に数兆の可能な組み合わせに成長し、一度に数兆の順列をメモリに保持することを PHP に任せたくないと言うだけで十分です。

4

4 に答える 4

2

申し訳ありませんがphpコードはありませんが、アルゴリズムを提供できます。

少量のメモリで実行でき、重複を気にしないため、コードも単純になります。

最初に: すべての可能なサブセットを生成します。

サブセットをビット ベクトルとして表示すると、セットと 2 進数に 1 対 1 の対応があることがわかります。

したがって、配列に 12 個の要素がある場合、2^12 個のサブセット (空のセットを含む) があります。

したがって、サブセットを生成するには、0 から開始し、2^12 に達するまでインクリメントし続けます。各段階で、数値のセット ビットを読み取り、配列から適切なサブセットを取得します。

1 つのサブセットを取得したら、その順列を実行できます。

次の順列 (要素自体ではなく、配列インデックスの) は、次のように辞書順で生成できます: http://www.de-brauwer.be/wiki/wikka.php?wakka=Permutations最小限のメモリー。

これら 2 つを組み合わせて、自分自身に next_permutation 関数を与えることができるはずです。数値を渡す代わりに、前の順列を含む 12 要素の配列を渡すことができます。また、次のサブセットに移動する必要があるかどうかなどの追加情報 (メモリも少し) を渡すこともできます。

実際には、最小限のメモリを使用し、next_permutation タイプの機能を提供し、重複を生成しない非常に高速なアルゴリズムを見つけることができるはずです。Web で multiset permutation/combination generation を検索してください。

それが役立つことを願っています。幸運を！

于 2010-06-11T01:40:09.027 に答える
1

私が思いついた関数の最良のセットは、php.net のシャッフル関数のコメントで一部のユーザーによって提供されたものでした。リンクは次のとおりです。かなりうまく機能します。

それが役に立つことを願っています。

于 2010-06-11T01:53:21.970 に答える
0

入力: 順列インデックス k、インデックス付きセット S。

擬似コード:

L = {S_1}
for i = 2 to |S| do
 Insert S_i before L_{k % i}
 k <- k / i
loop
return L

このアルゴリズムは、重複を処理するように簡単に変更することもできます。

于 2010-06-14T12:42:31.357 に答える
0

問題は、すべての順列にインデックスを付けようとしていて、アクセス時間が一定であるようです。一定時間のアルゴリズムは考えられませんが、これを改善できるかもしれません。このアルゴリズムの時間の複雑さは O(n) で、n はセットの長さです。スペースの複雑さは O(1) に削減できる必要があります。

セットが 1,1,2,3 で、10 番目の順列が必要だとします。また、セットの各要素に 0 から 3 までのインデックスを付けることに注意してください。順序に従って、これは単一要素の順列が最初に来て、次に 2 つの要素、というように続くことを意味します。10 番目の順列を完全に決定できるまで、10 から減算します。

最初は、単一要素の順列です。それらは 4 つあるので、これを 10 から 1 を 4 回引くと見なすことができます。残りは 6 であるため、明らかに 2 つの要素の順列を検討する必要があります。これらは 12 あり、これを 6 から 3 から 4 回引くと見なすことができます。2 回目に 3 を引くと、0 が残ることがわかります。これは、順列のインデックスが 2 でなければならないことを意味します (なぜなら、 3 を 2 回引いたもの) と 0 です。0 は剰余であるためです。したがって、順列は 2,1 でなければなりません。

除算とモジュラスが役立つ場合があります。

12 番目の順列を探していた場合、残りが 2 の場合に遭遇します。目的の動作によっては、順列 2,2 が有効でない場合があります。ただし、インデックス 2 と 2 (要素と混同しないでください) が同じであることを自明に検出できるため、これを回避するのは非常に簡単です。 2,3 として計算されます。

現在の最大の混乱は、インデックスと要素の値がたまたま一致することです。そのため、アルゴリズムの説明があまり混乱しないことを願っています。もしそうなら、私はあなたの例以外のセットを使用して物事を言い換えます.

于 2010-06-11T16:47:05.753 に答える