Nª Combinação

Existe uma maneira direta de obter a enésima combinação de um conjunto ordenado de todas as combinações de nCr?

Exemplo: eu tenho quatro elementos: [6, 4, 2, 1]. Todas as combinações possíveis, tomando três de cada vez, seriam: [[6, 4, 2], [6, 4, 1], [6, 2, 1], [4, 2, 1]].

Existe um algoritmo que me daria, por exemplo, a terceira resposta, [6, 2, 1], no conjunto de resultados ordenados, sem enumerar todas as respostas anteriores?

    Note que você pode gerar a sequência gerando recursivamente todas as combinações com o primeiro elemento, depois todas as combinações sem. Em ambos os casos recursivos, você solta o primeiro elemento para obter todas as combinações de elementos n-1. Em 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 

    Toda vez que você está gerando uma sequência fazendo uma escolha como essa, você pode gerar recursivamente o k- ésimo elemento contando quantos elementos uma escolha gera e comparando a contagem a k. Se k é menor que a contagem, você faz essa escolha. Caso contrário, subtraia a contagem e repita para as outras escolhas possíveis que você poderia fazer nesse momento. Se sempre houver opções, você pode ver isso como gerar um número na base b . A técnica ainda funciona se o número de escolhas variar. No pseudocódigo (quando todas as opções estão sempre disponíveis):

     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 

    Isto dá-lhe um índice baseado em 0. Se você quiser baseado em 1, altere a comparação para k <= size of choice .

    A parte difícil (e não especificada no pseudocódigo) é que o tamanho de uma escolha depende das escolhas anteriores. Observe que o pseudocódigo pode ser usado para resolver um caso mais geral do que o problema.

    Para este problema específico, existem duas opções ( b = 2) e o tamanho da 1ª escolha (isto é, incluindo o elemento) é dado por n-1 C r-1 . Aqui está uma implementação (que requer um nCr adequado):

     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(ki, l[1:], r) 

    Se você inverter a ordem das escolhas, inverterá a ordem da seqüência.

     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(ki, l[1:], r-1) 

    Colocando para usar:

     >>> 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] 
    • TLDR? Basta ir até o final da minha solução final .

    Eu tropecei nessa questão enquanto procurava methods para obter o índice em que uma combinação especificada estaria localizada se estivesse em uma lista ordenada lexicograficamente e vice-versa , para uma escolha de objects de um conjunto potencialmente grande de objects e poderia encontre muito neste último (o inverso do seu problema não é tão elusivo).

    Desde que eu também resolvi (o que eu pensava que era) o seu problema exato antes que eu pensasse em postar minhas soluções para ambos aqui.

    **
    EDIT: Minha exigência é o que sua exigência foi também – eu vi as respostas e pensei que a recursion estava bem. Bem, agora, depois de seis longos anos você tem isso; basta rolar para baixo.
    **

    Para sua exigência como (eu pensei que fosse) colocada na questão, isso fará o trabalho muito bem:

     def iterCombinations(n, k): if k==1: for i in range(n): yield [i] return result = [] for a in range(k-1, n): for e in iterCombinations(n, k-1): if e[-1] == a: break yield e + [a] 

    Você pode então procurar o item em uma coleção ordenada na ordem decrescente (ou usar alguma metodologia de comparação equivalente), portanto, para o caso em questão:

     >>> itemsDescending = [6,4,2,1] >>> for c in iterCombinations(4, 3): ... [itemsDescending[i] for i in c] ... [6, 4, 2] [6, 4, 1] [6, 2, 1] [4, 2, 1] 

    Isso também é possível imediatamente em Python, no entanto:

     >>> import itertools >>> for c in itertools.combinations(itemsDescending, 3): ... c ... (6, 4, 2) (6, 4, 1) (6, 2, 1) (4, 2, 1) 

    Aqui está o que eu fiz para minha exigência (e realmente para a sua!) De um algoritmo não recursivo que não cria ou percorre a lista ordenada para qualquer direção, mas usa uma implementação simples, mas eficaz, não recursiva de n C r , escolha (n, k):

     def choose(n, k): '''Returns the number of ways to choose k items from n items''' reflect = n - k if k > reflect: if k > n: return 0 k = reflect if k == 0: return 1 for nMinusIPlus1, i in zip(range(n - 1, n - k, -1), range(2, k + 1)): n = n * nMinusIPlus1 // i return n 

    Para obter a combinação em algum índice (baseado em zero) em uma lista classificada de encaminhamento :

     def iterCombination(index, n, k): '''Yields the items of the single combination that would be at the provided (0-based) index in a lexicographically sorted list of combinations of choices of k items from n items [0,n), given the combinations were sorted in descending order. Yields in descending order. ''' if index < 0 or index >= choose(n, k): return n -= 1 for i in range(k): while choose(n, k) > index: n -= 1 yield n index -= choose(n, k) n -= 1 k -= 1 

    Para obter o índice (baseado em zero) no qual alguma combinação residiria em uma lista ordenada inversa :

     def indexOfCombination(combination): '''Returns the (0-based) index the given combination would have if it were in a reverse-lexicographically sorted list of combinations of choices of len(combination) items from any possible number of items (given the combination's length and maximum value) - combination must already be in descending order, and it's items drawn from the set [0,n). ''' result = 0 for i, a in enumerate(combination): result += choose(a, i + 1) return result 

    É um exagero para o seu exemplo (mas agora percebo que isso foi apenas um exemplo); é assim que isso iria para cada índice, por sua vez:

     def exampleUseCase(itemsDescending=[6,4,2,1], k=3): n = len(itemsDescending) print("index -> combination -> and back again:") for i in range(choose(n, k)): c = [itemsDescending[j] for j in iterCombination(i, n, k)][-1::-1] index = indexOfCombination([itemsDescending.index(v) for v in c]) print("{0} -> {1} -> {2}".format(i, c, index)) >>> exampleUseCase() index -> combination -> and back again: 0 -> [6, 4, 2] -> 0 1 -> [6, 4, 1] -> 1 2 -> [6, 2, 1] -> 2 3 -> [4, 2, 1] -> 3 

    Isso pode encontrar o índice dado uma lista longa ou retornar a combinação em algum índice astronômico em um piscar de olhos , por exemplo:

     >>> choose(2016, 37) 9617597205504126094112265433349923026485628526002095715212972063686138242753600 >>> list(iterCombination(_-1, 2016, 37)) [2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986, 1985, 1984, 1983, 1982, 1981, 1980, 1979] 

    ou, desde que foi o último e pode ser rápido devido ao reflexo na escolha (n, k), aqui está um da direita no meio e parece tão rápido …

     >>> choose(2016, 37)//2 4808798602752063047056132716674961513242814263001047857606486031843069121376800 >>> list(iterCombination(_, 2016, 37)) [1978, 1973, 1921, 1908, 1825, 1775, 1747, 1635, 1613, 1598, 1529, 1528, 1521, 1445, 1393, 1251, 1247, 1229, 1204, 1198, 922, 901, 794, 699, 685, 633, 619, 598, 469, 456, 374, 368, 357, 219, 149, 93, 71] 

    Este último exemplo faz uma pausa para pensar por uma fração de segundo, mas não é?

     >>> import random >>> rSet = set(random.randint(0, 10000000) for i in range(900)) >>> len(rSet) 900 >>> rList = sorted(rSet, reverse=True) >>> combinations.indexOfCombination(rList) 61536587905102303838316048492163850175478325236595592744487336325506086930974887 88085020093159925576117511028315621934208381981476407812702689774826510322023536 58905845549371069786639595263444239118366962232872361362581506476113967993096033 00541202874946853699568596881200225925266331936183173583581021914595163799417151 30442624813775945054888304722079206982972852037480516813527237183254850056012217 59834465303543702263588008387352235149083914737690225710105023486226582087736870 38383323140972279867697434315252036074490127510158752080225274972225311906715033 86851377357968649982293794242170046400174118714525559851836064661141086690326842 25236658978135989907667078625869419802333512020715700514133380517628637151215549 05922388534567108671308819960483147825031620798631811671493891643972220604919591 22785587505280326638477135315176731640100473359830821781905546117103137944239120 34912084544221250309244925308316352643060056100719194985568284049903555621750881 39419639825279398618630525081169688672242833238889454445237928356800414839702024 66807635358129606994342005075585962080795273287472139515994244684088406544976674 84183671032002497594936116837768233617073949894918741875863985858049825755901232 89317507965160689287607868119414903299382093412911433254998227245783454244894604 83654290108678890682359278892580855226717964180806265176337132759167920384512456 91624558534942279041452960272707049107641475225516294235268581475735143470692000 78400891862852130481822509803019636619427631175355448729708451565341764545325720 79277290914349746541071731127111532099038538549697091038496002102703737347343739 96398832832674081286904287066696046621691978697914823322322650123025472624927566 99891468668052668317066769517155581261265629289158798073055495539590686279250097 27295943276536772955923599217742543093669565147228386873469711200278811335649924 13587219640724942441913695193417732608127949738209466313175361161142601108707568 19470026889319648128790363676253707359290547393198350533094409863254710237344552 47692325209744353688541868412075798500629908908768438513508959321262250985142709 19794478379412756202638771417821781240327337108495689300616872374578607430951230 96908870723878513999404242546015617238957825116802801618973562178005776911079790 22026655573872019955677676783191505879571719659770550759779880002320421606755826 75809722478174545846409923210824885805972611279030267270741509747224602604003738 30411365119180944456819762167312738395140461035991994771968906979578667047734952 21981545694935313345331923300019842406900689401417602004228459137311983483386802 30352489602769346000257761959413965109940729263098747702427952104316612809425394 85037536245288888254374135695390839718978818689595231708490351927063849922772653 26064826999661128817511630298712833048667406916285156973335575847429111697259113 53969532522640227276562651123634766230804871160471143157687290382053412295542343 14022687833967461351170188107671919648640149202504369991478703293224727284508796 06843631262345918398240286430644564444566815901074110609701319038586170760771099 41252989796265436701638358088345892387619172572763571929093224171759199798290520 71975442996399826830220944004118266689537930602427572308646745061258472912222347 18088442198837834539211242627770833874751143136048704550494404981971932449150098 52555927020553995188323691320225317096340687798498057634440618188905647503384292 79493920419695886724506109053220167190536026635080266763647744881063220423654648 36855624855494077960732944499038847158715263413026604773216510801253044020991845 89652657529729792772055725210165026891724511953666038764273616212464901231675592 46950937136633665320781952510620087284589083139308516989522633786063418913473703 96532777760440118656525488729217328376766171004246127636983612583177565603918697 15557602015171235214344399010185766876727226408494760175957535995025356361689144 85181975631986409708533731043231896096597038345028523539733981468056497208027899 6245509252811753667386001506195 

    No entanto, voltar desse índice para a combinação de 900.000.000.000.000 que ele representa com a implementação anterior seria muito lento (já que ele simplesmente subtrai um de n a cada iteração).

    Para listas tão grandes de combinações, podemos fazer uma pesquisa binária do espaço, e a sobrecarga que adicionamos significa que será apenas um pouco mais lenta para pequenas listas de combinações:

     def iterCombination(index, n, k): '''Yields the items of the single combination that would be at the provided (0-based) index in a lexicographically sorted list of combinations of choices of k items from n items [0,n), given the combinations were sorted in descending order. Yields in descending order. ''' if index < 0 or n < k or n < 1 or k < 1 or choose(n, k) <= index: return for i in range(k, 0, -1): d = (n - i) // 2 or 1 n -= d while 1: nCi = choose(n, i) while nCi > index: d = d // 2 or 1 n -= d nCi = choose(n, i) if d == 1: break n += d d //= 2 n -= d yield n index -= nCi 

    A partir disso, pode-se notar que todas as chamadas para choose têm termos que cancelam, se cancelarmos tudo, acabamos com uma implementação muito mais rápida e o que é, eu acho …

    A ótima function para este problema

     def iterCombination(index, n, k): '''Yields the items of the single combination that would be at the provided (0-based) index in a lexicographically sorted list of combinations of choices of k items from n items [0,n), given the combinations were sorted in descending order. Yields in descending order. ''' nCk = 1 for nMinusI, iPlus1 in zip(range(n, n - k, -1), range(1, k + 1)): nCk *= nMinusI nCk //= iPlus1 curIndex = nCk for k in range(k, 0, -1): nCk *= k nCk //= n while curIndex - nCk > index: curIndex -= nCk nCk *= (n - k) nCk -= nCk % k n -= 1 nCk //= n n -= 1 yield n 

    Um lembrete final de que, para o caso de uso da pergunta um, faria algo assim:

     def combinationAt(index, itemsDescending, k): return [itemsDescending[i] for i in list(iterCombination(index, len(itemsDescending), k))[-1::-1]] >>> itemsDescending = [6,4,2,1] >>> numberOfItemsBeingChosen = 3 >>> zeroBasedIndexWanted = 1 >>> combinationAt(zeroBasedIndexWanted, itemsDescending, numberOfItemsBeingChosen) [6, 4, 1] 

    Uma maneira de fazer isso seria usando propriedades de bits. Isso ainda requer alguma enumeração, mas você não teria que enumerar todos os conjuntos.

    Por exemplo, você tem 4 números no seu conjunto. Então, se você estivesse gerando todas as combinações possíveis de 4 números, poderia enumerá-los da seguinte maneira:

     {6, 4, 2, 1}
    
     0000 - {(sem números no conjunto)}
     0001 - {1}
     0010 - {2}
     0011 - {2, 1}
     ...
     1111 - {6, 4, 2, 1}
    

    Veja como cada “bit” corresponde a “se esse número está no seu conjunto”? Vemos aqui que existem 16 possibilidades (2 ^ 4).

    Então agora podemos percorrer e encontrar todas as possibilidades que têm apenas 3 bits ativados. Isso nos dirá todas as combinações de “3” que existem:

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

    E vamos rewrite cada um dos nossos valores binários como valores decimais:

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

    Agora que fizemos isso – bem, você disse que queria a enumeração “3ª”. Então vamos dar uma olhada no terceiro maior número: 11. Que tem o padrão de bits 1011. Que corresponde a … {6, 2, 1}

    Legal!

    Basicamente, você pode usar o mesmo conceito para qualquer conjunto. Então agora tudo o que fizemos foi traduzir o problema de “enumerando todos os conjuntos” para “enumerando todos os inteiros”. Isso pode ser muito mais fácil para o seu problema.

    Das receitas do Python 3.6 itertools :

     def nth_combination(iterable, r, index): 'Equivalent to list(combinations(iterable, r))[index]' pool = tuple(iterable) n = len(pool) if r < 0 or r > n: raise ValueError c = 1 k = min(r, nr) for i in range(1, k+1): c = c * (n - k + i) // i if index < 0: index += c if index < 0 or index >= c: raise IndexError result = [] while r: c, n, r = c*r//n, n-1, r-1 while index >= c: index -= c c, n = c*(nr)//n, n-1 result.append(pool[-1-n]) return tuple(result) 

    Na prática:

     iterable, r, index = [6, 4, 2, 1], 3, 2 nth_combination(iterable, r, index) # (6, 2, 1) 

    Como alternativa, conforme mencionado no docstring:

     import itertools as it list(it.combinations(iterable, r))[index] # (6, 2, 1) 

    Veja também more_itertools – uma biblioteca de terceiros que implementa esta receita para você. Instalar via:

     > pip install more_itertools 

    apenas um esboço: organize seus números em uma matriz triangular superior de tuplas:

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

    Se você percorrer primeiro a linha da matriz, obterá combinações em ordem crescente para dois elementos. Para generalizar para três elementos, pense em suas linhas de matriz como outra matriz triangular, em vez de um vetor. Isso meio que cria um canto de um cubo.

    Pelo menos é assim que eu abordaria o problema

    deixe-me esclarecer isso, você não tem que armazenar a matriz, você precisará calcular o índice. Deixe-me trabalhar para o exemplo dimensional, que você, em princípio, poderia expandir para 20 dimensões (a contabilidade pode ser atroz).

     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 

    esse exemplo bidimensional funciona para qualquer número n e você não precisa tabular permutações.