先行するすべての順列を生成せずに、セットの N 番目の順列を直接見つけるにはどうすればよいでしょうか?

n 番目の順列を直接取得する

このタスクは、すべてを明示的に計算せずに要素セットの n 番目の順列を見つけることです。以前の順列。これは、Factoradic アルゴリズムと呼ばれる賢いアルゴリズムを使用して実現できます。

Factoradic アルゴリズムは、置換インデックスの階乗分解を利用します。階乗数を使用してユークリッド除算を繰り返し実行することで、順列を表す商のセットが得られます。

アルゴリズムの仕組みは次のとおりです:

1. 階乗分解:置換インデックス n を (n-1)!、(n-2)!、および (n-2)! の階乗で割ります。 すぐ。商は配列に保存されます。
2. 順列表現: 各商は、残りの要素から選択された要素のインデックスを表します。
3. 調整: 商は前の値を考慮しないため、正しい順列を反映するように調整する必要があります。各商を、それ以下の先行する商の数だけ増分します。

たとえば、{'A', 'B', 'C'} の 3 番目の順列を見つけてみましょう。

• n = 3
• 商: [1, 0, 0]
• 調整商: [1, 0, 1]

したがって、順列は 'B'、'A'、'C' となり、これは次のようになります。実際、指定されたセットの 3 番目の順列です。

提供された C コードは Factoradic を実装します。前の順列を計算せずに n 番目の順列を直接取得する方法を示すアルゴリズム。

以上が先行するすべての順列を生成せずに、セットの N 番目の順列を直接見つけるにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。