6

次のシナリオを考えてみましょう。

私は数字の配列を持っています：

 [ 1,2,3,4 ]

この配列が結合された場合、番号は1234になります。

数字を入れ替えて、最も高い数字を実現したいと思います。

1234は1243になり、1324になり、1342になります。

アレイでこの変更を行うには、どのアルゴリズムを使用する必要がありますか？

理想的には、この方法でアルゴリズムを使用したいと思います:(配列がウォークスルーと呼ばれる関数としてこのアルゴリズムを持っているとしましょう）

 [ 1,2,3,4].walkthrough() # gives [ 1, 2, 4, 3 ]
 [ 1,2,4,3].walkthrough() # gives [ 1, 3, 2, 4 ]

番号のリストは続きます：

1234
1243
1324
1342
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241

4

2 に答える 2

9

これにより、次の順列が得られます。

bool Increase(int[] values) {
   // locate the last item which is smaller than the following item
   int pos = values.Length - 2;
   while (pos >= 0 && values[pos] > values[pos + 1]) pos--;
   // if not found we are done
   if (pos == -1) return false;
   // locate the item next higher in value
   int pos2 = values.Length - 1;
   while (values[pos2] < values[pos]) pos2--;
   // put the higher value in that position
   int temp = values[pos];
   values[pos] = values[pos2];
   values[pos2] = temp;
   // reverse the values to the right
   Array.Reverse(values, pos + 1, values.Length - pos - 1);
   return true;
}

編集：
Array.SortをArray.Reverseに変更しました。アイテムは常に降順であり、昇順である必要があるため、同じ結果が得られます。

于 2009-08-27T19:48:54.563 に答える
6

これは、リストの順列を辞書式順序で生成したいようです。これらの検索用語は、有用な道を歩み始めるはずです。

たとえば、Pythonはこれをバージョン2.6以降のitertoolsモジュールに含めています。そのドキュメントは、そのようなアルゴリズムを実装するコードを示しています。

于 2009-08-27T19:19:07.730 に答える