4

与えられた値のセットのすべての可能な順列を生成するための多くのアルゴリズムがあります。通常、これらの値は、O(1) ランダム アクセスを持つ配列として表されます。

ただし、置換する要素が二重にリンクされたリストとして表されているとします。この場合、リスト内の要素に O(1) 時間でランダムにアクセスすることはできないため、多くの置換アルゴリズムで不要な速度低下が発生します。

リンクされたリストのすべての可能な順列を可能な限り少ない時間とスペースのオーバーヘッドで生成するアルゴリズムはありますか?

4

4 に答える 4

4

一枚の紙の上にすべての順列を生成する方法を考えてみてください。

右端の数字から開始し、隣の数字よりも小さい数字が表示されるまで、1 つ左に移動します。次の値の数字をそこに配置し、残りのすべての数字をその後の昇順で並べ替えます。何もすることがなくなるまでこれを行います。少し考えてみると、数値に関して線形時間で数値を並べ替えることができます。

実際、これは私が知る限り、次の順列に使用される典型的なアルゴリズムです。これがリストよりも配列の方が高速になる理由はわかりません。

于 2013-01-10T20:58:59.873 に答える
2

Steinhaus–Johnson–Trotter アルゴリズムを調べるとよいでしょう。隣接する要素を交換することによってのみ、シーケンスのすべての順列を生成します。二重リンクリストの O(1) でできること。

于 2013-01-10T21:33:02.267 に答える
1

リンクされたリストのデータを配列に読み込む必要があります。配列はO(n)ヒープの順列 ( http://www.geekviewpoint.com/java/numbers/permutation ) を取得して使用し、すべての順列を見つけます。

于 2013-01-11T03:28:36.917 に答える
0

Factoradic Permutation Algorithmを使用し、それに応じてノード ポインターを再配置して、結果の順列を再帰なしでその場で生成できます。

疑似説明:

element_to_permute = list
temp_list = new empty list
for i = 1 in n! 
   indexes[] = factoradic(i)
   for j in indexes[]
      rearrange pointers of node `indexes[j]` of `element_to_permute` in `temp_list`
于 2013-01-10T21:50:33.470 に答える