PHP：26文字からX文字の順列

Question

26文字A..Zのアルファベット配列を持っています。

私は、長さXの配列を繰り返し文字なしで並べ替えるすべての並べ替えをリストする実行アルゴリズムを探しています。

例：

X = 3。ターゲット配列：_ _ _

順列は、Z Y XまでA B Cです。

X = 4。標的配列：_ _ _ _

順列は、Z Y X WまでB C D

X = 5です。ターゲット配列：_ _ _ _ _

順列は、Z Y X W V

（申し訳ありませんが、私はこの種のアルゴリズムがどのように命名されるか分からない）まで事前に

おかげB C D Eです。

C、Delphi、Javaのコードも簡単に翻訳できるので、OKです。

Answer 1

数字が26であるので、順列の数が増えることは理解していますが、私は単純な強引なアプローチをとっています！/（26-x）！ 3の場合は15,600の順列があり、5の場合は7,893,600の順列があり、正確には小さいわけではありません。基本的には、残念ながらO（n^x）のループ内のループですべての値をループすることができます。ここで、xは複雑さの原因となるループのネストから文字の数です。

---

ここでは複雑さをどの程度細かく検討していますか。たとえば、重複を避けるためにループの最初のペアで巧みにする方法を検討することができますが、26文字のリストで開始し、前のものを削除した場合、3番目のループはやや厄介になります最後のループは、重複していないことを知っているので単純に繰り返します。これは、外部ループからの各パスでリストのコピーを作成する際に消費されるメモリの点で高価になる可能性があります。したがって、最初はAB_を経てAC_などに行きますが、リストのコピーは、リストがコピーされて何千もの時間がかかるために、操作上のコストがかかる場合がありますそれが比較を行うよりも効率的ならば。

Answer 2

すべての並べ替えを表示してもよろしいですか？ X = 3の場合、26 * 25 * 24の組み合わせ= 15600となります.X = 5の場合、組み合わせの数は7893600になります。

ランダムに1文字（または配列インデックス）それはどこかにあり、繰り返しごとに、以前の繰り返しの1つでこの文字（またはインデックス）がすでに選択されているかどうかを確認する必要があります。この後、長さがX文字のランダムなシーケンスが得られます。あなたもそれを保存する必要があります。その後、前のステップで行ったすべての操作を再設定する必要があります。また、現在生成しているサブシーケンスとのランダムなシーケンスがあるかどうかをチェックする必要があります。

また、直接列挙を使用することもできます。

申し訳ございませんが、英語が不満です。私は明確にしようとした。

私はそれが役に立ちそうです。

Answer 3

簡単な解決策は、上記の関数が計算される文字との組み合わせの文字の総数n（コードi<nを想定）のインデックスiを受け付ける再帰1

char current_combination[27]; 
int char_used[26]; 

void enumerate(int i, int n) 
{ 
    for (int j=0; j<26; j++) 
    { 
     if (!char_used[j]) 
     { 
      char_used[j] = 1; 
      current_combination[i] = 'A' + j; 
      if (i+1 == n) 
      { 
       puts(current_combination); 
      } 
      else 
      { 
       enumerate(i+1, n); 
      } 
      char_used[j] = 0; 
     } 
    } 
} 

あります。現在の組み合わせと、すでに使用されている変数のフラグの配列をグローバルに保持して、それらをコピーしないようにします。

たとえば、長さ5のすべての組み合わせを生成するには、enumerate(0, 5)を呼び出します。

合計の組み合わせ数は、が非常にと大きくなることに注意してください。例えば、n=6の場合は、165,765,600の組み合わせがあり、1Gb以上の出力があります。