16

nCrのすべての組み合わせの順序集合のN番目の組み合わせを取得する直接的な方法はありますか？

例：[6、4、2、1]の4つの要素があります。一度に3つを取ることによって可能なすべての組み合わせは次のようになります：[[6、4、2]、[6、4、1]、[6、2、1]、[4、2、1]]。

以前のすべての回答を列挙せずに、順序付けられた結果セットの3番目の回答[6、2、1]などを取得するアルゴリズムはありますか？

4

6 に答える 6

17

最初の要素を含むすべての組み合わせを再帰的に生成し、次に要素を含まないすべての組み合わせを再帰的に生成することにより、シーケンスを生成できることに注意してください。どちらの再帰的な場合でも、最初の要素を削除して、n-1 個の要素からすべての組み合わせを取得します。Python の場合:

def combination(l, r):
    if r == 0:
        yield []
    elif len(l) == r:
        yield l
    else:
        for c in (combination(l[1:], r-1)):
            yield l[0:1]+c
        for c in (combination(l[1:], r)):
            yield c

このような選択を行ってシーケンスを生成するときはいつでも、選択によって生成される要素の数をカウントし、そのカウントを k と比較することにより、k番目の要素を再帰的に生成できます。k がカウントより小さい場合は、その選択を行います。それ以外の場合は、カウントを減算し、その時点で可能な他の選択肢について繰り返します。b選択肢が常にある場合は、これを base で数値を生成していると見なすことができますb。選択肢の数が異なる場合でも、この手法は機能します。擬似コード (すべての選択肢が常に利用可能な場合):

kth(k, choicePoints)
    if choicePoints is empty
        return empty list
    for each choice in head of choicePoints:
        if k < size of choice
            return choice and kth(k, tail of choicePoints)
        else
            k -= size of choice
    signal exception: k is out-of-bounds

これにより、0 ベースのインデックスが得られます。1 ベースが必要な場合は、比較を に変更しk <= size of choiceます。

注意が必要な部分 (および疑似コードで指定されていないこと) は、選択のサイズが以前の選択に依存することです。擬似コードは、問題よりも一般的なケースを解決するために使用できることに注意してください。

この特定の問題では、2 つの選択肢 ( b= 2) があり、最初の選択肢 (つまり、最初の要素を含む) のサイズはn-1 C r -1で与えられます。1 つの実装を次に示します (適切な が必要です)。nCr

def kthCombination(k, l, r):
    if r == 0:
        return []
    elif len(l) == r:
        return l
    else:
        i=nCr(len(l)-1, r-1)
        if k < i:
            return l[0:1] + kthCombination(k, l[1:], r-1)
        else:
            return kthCombination(k-i, l[1:], r)

選択肢の順序を逆にすると、シーケンスの順序が逆になります。

def reverseKthCombination(k, l, r):
    if r == 0:
        return []
    elif len(l) == r:
        return l
    else:
        i=nCr(len(l)-1, r)
        if k < i:
            return reverseKthCombination(k, l[1:], r)
        else:
            return l[0:1] + reverseKthCombination(k-i, l[1:], r-1)

それを使用する：

>>> l = [6, 4, 2, 1]
>>> [kthCombination(k, [6, 4, 2, 1], 3) for k in range(nCr(len(l), 3)) ]
[[6, 4, 2], [6, 4, 1], [6, 2, 1], [4, 2, 1]]
>>> powOf2s=[2**i for i in range(4,-1,-1)]
>>> [sum(kthCombination(k, powOf2s, 3)) for k in range(nCr(len(powOf2s), 3))]
[28, 26, 25, 22, 21, 19, 14, 13, 11, 7]
>>> [sum(reverseKthCombination(k, powOf2s, 3)) for k in range(nCr(len(powOf2s), 3))]
[7, 11, 13, 14, 19, 21, 22, 25, 26, 28]
于 2009-11-21T21:40:10.350 に答える
8

それを行う 1 つの方法は、ビットのプロパティを使用することです。これにはまだいくつかの列挙が必要ですが、すべてのセットを列挙する必要はありません。

あなたの例では、セットに 4 つの数字があります。したがって、4 つの数字の可能な組み合わせをすべて生成する場合、次のように列挙できます。

{6, 4, 2, 1}

0000 - {(数字がセットされていない)}
0001 - {1}
0010 - {2}
0011 - {2, 1}
...
1111 - {6, 4, 2, 1}

各「ビット」が「その数値がセット内にあるかどうか」にどのように対応するかを確認してください。ここでは、16 の可能性 (2^4) があることがわかります。

これで、3 ビットのみがオンになっているすべての可能性を調べて見つけることができます。これにより、存在する「3」の組み合わせがすべてわかります。

0111 - {4, 2, 1}
1011 - {6, 2, 1}
1101 - {6, 4, 1}
1110 - {6, 4, 2}

そして、各バイナリ値を 10 進数値として書き直してみましょう。

0111 = 7
1011 = 11
1101 = 13
1110 = 14

これで、「3番目」の列挙が必要だとおっしゃいましたね。では、3 番目に大きい数 11 を見てみましょう。ビット パターンは 1011 です。これは、{6, 2, 1} に対応します。

涼しい！

基本的に、どのセットにも同じ概念を使用できます。これで、問題を「すべてのセットを列挙する」から「すべての整数を列挙する」に変換しただけです。これはあなたの問題にとってはるかに簡単かもしれません。

于 2009-11-21T20:20:34.180 に答える
2

大まかなスケッチ: 数値をタプルの上三角行列に配置します。

A(n-1,n-1)   
Aij = [i+1, j-1]

最初に行列の行をトラバースすると、2 つの要素の組み合わせが昇順で取得されます。3 つの要素に一般化するには、行列の行をベクトルではなく別の三角行列と考えてください。立方体のコーナーを作成するようなものです。

少なくともこれは私が問題にアプローチする方法です

これを明確にさせてください。行列を保存する必要はありません。インデックスを計算する必要があります。原則として20次元に拡張できる次元の例を考えてみましょう（簿記はひどいかもしれません）。

ij = (i*i + i)/2 + j // ij is also the combination number
(i,j) = decompose(ij) // from ij one can recover i,j components
I = i // actual first index
J = j + 1 // actual second index

この 2 次元の例は任意の数 n に対して機能し、順列を表にする必要はありません。

于 2009-11-21T19:58:01.010 に答える
0

はい、nCr のすべての組み合わせの順序付けられたセットの N 番目の組み合わせを取得する直接的な方法はありますか? 特定のセットの 0 番目、3 番目、6 番目.. の組み合わせを生成する必要があるとします。JNuberTools を使用する間に組み合わせを生成せずに直接生成できます。次の 10 億番目の組み合わせを生成することもできます (セットのサイズが大きい場合)。コード例は次のとおりです。

JNumberTools.combinationsOf(list)
        .uniqueNth(8,1000_000_000) //skip to billionth combination of size 8
        .forEach(System.out::println);

JNumberTools の Maven 依存関係は次のとおりです。

<dependency>
    <groupId>io.github.deepeshpatel</groupId>
    <artifactId>jnumbertools</artifactId>
    <version>1.0.0</version>
</dependency>
于 2021-07-13T06:45:58.183 に答える