7

k最初のn自然数の組み合わせを考えると、何らかの理由で、によって返されるものの中からそのような組み合わせの位置を見つける必要がありますitertools.combination(range(1,n),k)（この方法では、のlist代わりにを使用しdictて、各組み合わせに関連付けられた値にアクセスできます。組み合わせ）。

規則的なパターンでその組み合わせを生成するのでitertools、それを行うことは可能です（そして私はまたきちんとしたアルゴリズムを見つけました）が、私は無視するかもしれないさらに速く/自然な方法を探しています。

ちなみにここに私の解決策があります：

def find_idx(comb,n):
    k=len(comb)
    idx=0
    last_c=0
    for c in comb:
        #idx+=sum(nck(n-2-x,k-1) for x in range(c-last_c-1)) # a little faster without nck caching
        idx+=nck(n-1,k)-nck(n-c+last_c,k) # more elegant (thanks to Ray), faster with nck caching
        n-=c-last_c
        k-=1
        last_c=c
    return idx

ここで、n、kの二項係数をnck返します。

例えば：

comb=list(itertools.combinations(range(1,14),6))[654] #pick the 654th combination
find_idx(comb,14) # -> 654

そして、これは同等ですが、おそらくそれほど複雑ではないバージョンです（実際には、前のバージョンを次のバージョンから派生させました）。組み合わせの整数をc2進数の1の位置と見なし、0/1の解析でバイナリツリーを構築し、解析中にインデックス増分の規則的なパターンを見つけました。

def find_idx(comb,n):
    k=len(comb)
    b=bin(sum(1<<(x-1) for x in comb))[2:]
    idx=0
    for s in b[::-1]:
        if s=='0':
            idx+=nck(n-2,k-1)
        else:
            k-=1
        n-=1
    return idx
4

3 に答える 3

1

あなたの解決策はかなり速いようです。にはfind_idx、2つのforループがあり、内部ループは次の式を使用して最適化できます。

C(n, k) + C(n-1, k) + ... + C(n-r, k) = C(n+1, k+1) - C(n-r, k+1)

sum(nck(n-2-x,k-1) for x in range(c-last_c-1))したがって、に置き換えることができますnck(n-1, k) - nck(n-c+last_c, k)。

関数をどのように実装するかはわかりませんがnck(n, k)、時間計算量でO（k）を測定する必要があります。ここに私の実装を提供します：

from operator import mul
from functools import reduce # In python 3
def nck_safe(n, k):
    if k < 0 or n < k: return 0
    return reduce(mul, range(n, n-k, -1), 1) // reduce(mul, range(1, k+1), 1)

最後に、ソリューションは再帰なしでO（k ^ 2）になります。k大きすぎないのでかなり速いです。

アップデート

nckのパラメータがであることに気づきました(n, k)。nとkの両方が大きくなりすぎることはありません。キャッシュによってプログラムを高速化する場合があります。

def nck(n, k, _cache={}):
    if (n, k) in _cache: return _cache[n, k]
    ....
    # before returning the result
    _cache[n, k] = result
    return result

functools.lru_cachepython3では、これはデコレータを使用して実行できます。

@functools.lru_cache(maxsize=500)
def nck(n, k):
    ...
于 2013-01-30T15:21:56.780 に答える
0

タスクをより適切に指定する必要があるようです。そうでない場合、間違っています。私にとっては、反復処理するときにitertools.combinationインデックスを適切なデータ構造に保存できるようです。あなたがそれらのすべてを必要とするならば、私はdict（dictあなたのすべての必要性のための1つ）で行きます：

combinationToIdx = {}
for (idx, comb) in enumerate(itertools.combinations(range(1,14),6)):
    combinationToIdx[comb] = idx

def findIdx(comb):
    return combinationToIdx[comb]
于 2013-01-22T21:21:00.267 に答える
0

私はあなたが要求したことを実行する関数を含むいくつかの古い（Python 3構文に変換されていますが）コードを掘り起こしましたcombination_index：

def fact(n, _f=[1, 1, 2, 6, 24, 120, 720]):
    """Return n!
    The “hidden” list _f acts as a cache"""
    try:
        return _f[n]
    except IndexError:
        while len(_f) <= n:
            _f.append(_f[-1] * len(_f))
        return _f[n]

def indexed_combination(n: int, k: int, index: int) -> tuple:
    """Select the 'index'th combination of k over n
    Result is a tuple (i | i∈{0…n-1}) of length k

    Note that if index ≥ binomial_coefficient(n,k)
    then the result is almost always invalid"""

    result= []
    for item, n in enumerate(range(n, -1, -1)):
        pivot= fact(n-1)//fact(k-1)//fact(n-k)
        if index < pivot:
            result.append(item)
            k-= 1
            if k <= 0: break
        else:
            index-= pivot
    return tuple(result)

def combination_index(combination: tuple, n: int) -> int:
    """Return the index of combination (length == k)

    The combination argument should be a sorted sequence (i | i∈{0…n-1})"""

    k= len(combination)
    index= 0
    item_in_check= 0
    n-= 1 # to simplify subsequent calculations
    for offset, item in enumerate(combination, 1):
        while item_in_check < item:
            index+= fact(n-item_in_check)//fact(k-offset)//fact(n+offset-item_in_check-k)
            item_in_check+= 1
        item_in_check+= 1
    return index

def test():
    for n in range(1, 11):
        for k in range(1, n+1):
            max_index= fact(n)//fact(k)//fact(n-k)
            for i in range(max_index):
                comb= indexed_combination(n, k, i)
                i2= combination_index(comb, n)
                if i2 != i:
                    raise RuntimeError("mismatching n:%d k:%d i:%d≠%d" % (n, k, i, i2))

indexed_combination逆の操作を行います。

PS私は時々（適切な増分乗算と除算を置き換えることによって）これらの呼び出しをすべて削除しようとしたことを覚えていfactますが、コードははるかに複雑になり、実際には高速ではありませんでした。事前に計算された階乗のリストをfact関数に置き換えればスピードアップは達成できましたが、ユースケースでは速度の違いはごくわずかだったので、このバージョンを維持しました。

于 2016-09-17T20:37:29.010 に答える