2

この質問に基づいて

文字列の順序付けられた固定長の組み合わせ

固定長で文字の組み合わせを作成する PHP アルゴリズムを作成しました (基本的には Java の回答を書き直したものです)。

private function getCombination($length, $input) {
    $result = array();

    if ($length == 0) {
        return $result;
    }

    $first = substr($input, 0, $length);
    $result[] = $first;

    if (strlen($input) == $length) {
        return $result;
    }

    $tails = $this->getCombination($length - 1, substr($input, 1));

    foreach ($tails as $tail) {
        $tmp = substr($input, 0, 1) . $tail;

        if (!in_array($tmp, $result)) {
            $result[] = $tmp;
        }
    }

    return array_merge($result, $this->getCombination($length, substr($input, 1)));
}

別の質問、より大きなセットの固定長の非反復順列の作成については、順列をインデックス可能にする（素晴らしい）アルゴリズムが与えられ、与えられたときに常にまったく同じ順列を生成する「キー」を提供することで効果的にそれらをアドレス指定可能にします同じ文字セットと同じ長さ。

さて、基本的には同じものが必要ですが、他の質問の順列とは対照的に、組み合わせが必要です。

上記のアルゴリズムを同じように変更できますか? のような関数を作成する意味

public function getCombinationByIndex($length, $index);

それは、事前に作成せずにアルゴリズムで作成された1000の可能な組み合わせのうちの1つを返しますか?

4

1 に答える 1

1

二項係数を操作するための一般的な関数を処理するクラスを C# で作成しました。これは、順列ではなく組み合わせを操作することを前提として、問題が該当するように見える問題のタイプです。次のタスクを実行します。

  1. 任意の N choose K について、すべての K-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。

  2. K インデックスを、並べ替えられた二項係数テーブル内のエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的性質を使用して行われます。

  3. ソートされた二項係数テーブルのインデックスを対応する K インデックスに変換します。また、古い反復ソリューションよりも高速だと思います。

  4. Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。

  5. このクラスは .NET C# で記述されており、一般的なリストを使用して、問題に関連するオブジェクト (存在する場合) を管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれる bool 値を受け取ります。これが true の場合、管理対象のオブジェクトを保持する汎用リストが作成されます。この値が false の場合、テーブルは作成されません。上記の 4 つの方法を使用するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサ メソッドが用意されています。

  6. クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。2 つのケースで広範囲にテストされており、既知のバグはありません。

このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。

このクラスを php に移植するのはかなり簡単です。目標を達成するために、クラスのジェネリック部分を移植する必要はおそらくないでしょう。使用している組み合わせの数によっては、4 バイト整数よりも大きなワード サイズを使用する必要がある場合があります。

于 2012-11-07T17:20:28.040 に答える