属性順に組み合わせを生成する

https://stackoverflow.com/questions/523800

22-08-2019
|

質問

単一の属性によって順序付けされたオブジェクトの組み合わせを生成する方法を探しています。辞書順は私が探しているものではないと思います...例を挙げてみましょう。オブジェクト A、B、C、D のリストがあり、その属性値を 3、3、2、1 の順に並べたいとします。これにより、A3、B3、C2、D1 オブジェクトが得られます。ここで 2 つのオブジェクトの組み合わせを生成したいのですが、それらは降順で並べる必要があります。

A3 B3
A3 C2
B3 C2
A3 D1
B3 D1
C2 D1

現実世界のシナリオには大規模なセットと何百万もの組み合わせが含まれるため、すべての組み合わせを生成して並べ替えることは受け入れられません。(40個セット、8個注文)、特定のしきい値を超える組み合わせのみが必要です。

実際には、特定の属性の合計によってグループ化された、しきい値を超える組み合わせの数が必要ですが、それを実行するのははるかに難しいと思います。そのため、しきい値を超えるすべての組み合わせを開発し、それらをカウントすることにします。それが少しでも可能であれば。

編集 - 私の最初の質問はあまり正確ではありませんでした...実際にはこれらの組み合わせを順序付ける必要はありません。しきい値を超える組み合わせを分離するのに役立つと考えただけです。より正確に言うと、上記の例では、しきい値を 5 として、指定されたセットが合計 6 の組み合わせを 1 つ ( A3 B3 )、合計が 5 の組み合わせを 2 つ ( A3 C2, B3 C2)。実際には組み合わせ自体は必要ありません。

私は部分集合和の問題を調べていましたが、与えられた動的解法を正しく理解していれば、和の数ではなく、与えられた合計があるかないかという情報のみが得られます。

ありがとう

解決

実際、あなたはそう思いますする辞書編集上の順序が必要ですが、昇順ではなく降順です。加えて：

あなたの説明からは、A、B、... が明確ではありません。D は、回答の中で何らかの役割を果たします (値のコンテナとしての役割を除く)。
あなたの質問の例は、単純に「少なくとも 5 の各整数について、2 つの値の最大合計まで、その整数の合計を持つ集合 {3, 3, 2, 1} の異なるペアはいくつありますか?」というものだと思います。
興味深いのは、解決策に到達できなくなった場合（残りの達成可能な金額が少なすぎる場合）、早期に救済することです。

~~後ほどサンプルコードを投稿します。~~

これが私が約束したサンプルコードです。以下にいくつかの注釈を付け加えます。

public class Combos {

    /* permanent state for instance */
    private int values[];
    private int length;

    /* transient state during single "count" computation */
    private int n;
    private int limit;
    private Tally<Integer> tally;
    private int best[][];  // used for early-bail-out

    private void initializeForCount(int n, int limit) {
        this.n = n;
        this.limit = limit;
        best = new int[n+1][length+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length - i; ++j) {
                best[i][j] = values[j] + best[i-1][j+1];
            }
        }
    }

    private void countAt(int left, int start, int sum) {
        if (left == 0) {
            tally.inc(sum);
        } else {
            for (
                int i = start;
                i <= length - left
                && limit <= sum + best[left][i];  // bail-out-check
                ++i
            ) {
                countAt(left - 1, i + 1, sum + values[i]);
            }
        }
    }

    public Tally<Integer> count(int n, int limit) {
        tally = new Tally<Integer>();
        if (n <= length) {
            initializeForCount(n, limit);
            countAt(n, 0, 0);
        }
        return tally;
    }

    public Combos(int[] values) {
        this.values = values;
        this.length = values.length;
    }

}

序文:

これは、表作成 (これまでに見たことのないキーの初期化を含む) を分離するだけの、Tally と呼ばれる小さなヘルパークラスを使用します。最後に載せておきます。

簡潔にするために、「実際の」コードでは適切ではないいくつかのショートカットを採用しました。

これは、null 値の配列などはチェックしません。
早期救済手法に必要な値の配列がすでに降順にソートされていると仮定します。(優れた製品コードにはソートが含まれます。)
一時データをサポートするプライベートメソッド間の引数として渡すのではなく、インスタンス変数に入れます。 count. 。これにより、このクラスは非スレッドセーフになります。

説明：

の例 Combos 結合する整数の (降順) 配列を使用して作成されます。の value 配列はインスタンスごとに 1 回セットアップされますが、複数の呼び出しは count さまざまな人口サイズと制限を使用して作成できます。

の count このメソッドは、以下の一意の組み合わせの (主に) 標準的な再帰的走査をトリガーします。 n からの整数 values. 。の limit 引数は、利息の合計の下限を指定します。

の countAt メソッドは、次の整数の組み合わせを調べます。 values. 。の left 引数は、構成する整数がいくつ残っているかです。 n 合計の整数、 start の位置です values どこから検索するか、そして sum 部分和です。

早期救済メカニズムはコンピューティングに基づいています best, 、特定の状態から到達可能な「最良の」合計を指定する 2 次元配列。の値 best[n][p] の最大の合計です n 位置から始まる値 p オリジナルの values.

の再帰 countAt 正しい人口が蓄積されると底に達します。これは電流を追加します sum （の n 値) に tally. 。もし countAt 底を打っていない、一掃している values から start-ing 位置を指定して現在の部分を増加させます sum, 、に限って：

十分なポジションが残っている values 指定された人口を達成するために、そして
の best 残りの（最大の）小計は、 limit.

質問のデータを使用して実行したサンプル:

    int[] values = {3, 3, 2, 1};
    Combos mine = new Combos(values);
    Tally<Integer> tally = mine.count(2, 5);
    for (int i = 5; i < 9; ++i) {
        int n = tally.get(i);
        if (0 < n) {
            System.out.println("found " + tally.get(i) + " sums of " + i);
        }
    }

指定した結果が生成されます。

found 2 sums of 5
found 1 sums of 6

集計コードは次のとおりです。

public static class Tally<T> {
    private Map<T,Integer> tally = new HashMap<T,Integer>();
    public Tally() {/* nothing */}
    public void inc(T key) {
        Integer value = tally.get(key);
        if (value == null) {
            value = Integer.valueOf(0);
        }
        tally.put(key, (value + 1));
    }
    public int get(T key) {
        Integer result = tally.get(key);
        return result == null ? 0 : result;
    }
    public Collection<T> keys() {
        return tally.keySet();
    }
}

他のヒント

私は、あなたの問題が当てはまるタイプの問題である二項係数を扱うための一般的な関数を処理するクラスを作成しました。次のタスクを実行します。

K を選択した任意の N について、すべての K インデックスを適切な形式でファイルに出力します。K インデックスは、より説明的な文字列または文字に置き換えることができます。この方法を使用すると、この種の問題の解決が非常に簡単になります。
K インデックスを、ソートされた二項係数テーブル内のエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的性質を使用して行われます。私の論文はこれについて述べています。私はこのテクニックを最初に発見して公開したと信じていますが、間違っている可能性があります。
ソートされた二項係数テーブルのインデックスを対応する K インデックスに変換します。
用途マーク・ドミナス二項係数を計算する方法。オーバーフローの可能性がはるかに低く、より大きな数値でも機能します。
このクラスは .NET C# で記述されており、問題に関連するオブジェクト (存在する場合) を汎用リストを使用して管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれるブール値を受け取り、true の場合、管理対象のオブジェクトを保持する汎用リストを作成します。この値が false の場合、テーブルは作成されません。上記 4 つの方法を実行するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサーメソッドが提供されています。
クラスとそのメソッドの使用方法を示す、関連するテストクラスがあります。2 つのケースで広範囲にテストされており、既知のバグはありません。

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

stackoverflowの中でこの質問をチェックアウト：アルゴリズムへ返すすべての組み合わせでS

また、私はちょうどすべての順列を生成するには、以下のJavaコードを使用しますが、簡単にユニークな組み合わせのインデックス与えを生成するために使用することができます。

public static <E> E[] permutation(E[] s, int num) {//s is the input elements array and num is the number which represents the permutation

    int factorial = 1;

    for(int i = 2; i < s.length; i++)
        factorial *= i;//calculates the factorial of (s.length - 1)

    if (num/s.length >= factorial)// Optional. if the number is not in the range of [0, s.length! - 1] 
        return null;

    for(int i = 0; i < s.length - 1; i++){//go over the array

        int tempi = (num / factorial) % (s.length - i);//calculates the next cell from the cells left (the cells in the range [i, s.length - 1])
        E temp = s[i + tempi];//Temporarily saves the value of the cell needed to add to the permutation this time 

        for(int j = i + tempi; j > i; j--)//shift all elements to "cover" the "missing" cell
            s[j] = s[j-1];

        s[i] = temp;//put the chosen cell in the correct spot

        factorial /= (s.length - (i + 1));//updates the factorial

    }

    return s;
}

私は、この問題に対する効率的な解決策を見つけることができなかったことを言って（コメント内のすべてのものを明確化した後に）非常に残念です。ノー結果と過去の時間のために試してみました。

その理由は、（私が思う）この問題は、巡回セールスマン問題のような問題に非常によく似ているということです。あなたはすべての組み合わせを試していない限りまでは、しきい値件まで追加された属性を知る方法はありません。

問題のこのクラスを解決することができます何の巧妙なトリックはないように思われます。

それでもあなたは、実際のコードに行うことができます多くの最適化があります。

の属性に応じてデータをソートしてみます。あなたがより高い値がしきい値（ので、すべての低い値をなくすことができる）を満たすことができないことを見つけたとき、リストからいくつかの値の処理を回避できる可能性があります。

あなたがC＃を使用している場合は、

かなり良いジェネリックライブラリここのがあります。いくつかの順列の生成が辞書式順序ではないことに注意してくださいただし、

これは再帰的アプローチです カウント これらのサブセットの数:関数を定義します count(minIndex,numElements,minSum) サイズのサブセットの数を返します numElements 合計が少なくとも minSum, 、インデックス付きの要素を含む minIndex 以上。

問題文と同様に、要素を降順に並べ替えます。[3,3,2,1]、最初のインデックスをゼロ、要素の総数を N とします。すべての要素が非負であると仮定します。合計が 5 以上である 2 部分集合をすべて見つけるには、次のように呼び出します。 count(0,2,5).

サンプルコード (Java):

int count(int minIndex, int numElements, int minSum)
{
    int total = 0;

    if (numElements == 1)
    {
        // just count number of elements >= minSum
        for (int i = minIndex; i <= N-1; i++)
            if (a[i] >= minSum) total++; else break;
    }
    else
    {
        if (minSum <= 0)
        {
            // any subset will do (n-choose-k of them)
            if (numElements <= (N-minIndex))
                total = nchoosek(N-minIndex, numElements);
        }
        else
        {
            // add element a[i] to the set, and then consider the count
            // for all elements to its right
            for (int i = minIndex; i <= (N-numElements); i++)
                total += count(i+1, numElements-1, minSum-a[i]);
        }
    }

    return total;
}

ところで、私は 40 個の要素の配列とサイズ 8 のサブセットを使用して上記を実行し、1 秒以内に一貫して結果を返しました。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow