CODEWITHSUNDEEP
pythonrecursioncombinatorics
2Napasa
2Napasa

Reputation: 380

function for nCk chose k elements from list of n in python

I'm trying to write a function that makes nCk from the list in python

for example from the list for pairs: 

['a', 'b', 'c']

output should be:

[['a','b'],['a','c'],['b','c']]

however I'm getting no output

here's my attempt:

def chose(elements, k):
    output = []
    for i in range(len(elements)):
        if k == 1:
            output.append(elements[i])
        for c in chose(elements[i+1:], k-1):
            output.append(elements[i])
            output.append(c)
    return output
print chose(['a', 'b', 'c'],2)

can you kindly tell what is wrong with function

Upvotes: 1

Views: 506

Answers (2)

miindlek
miindlek

Reputation: 3563

Use itertools.combinations if you want to find all combinations:

from itertools import combinations

a = ['a', 'b', 'c']
result = [list(i) for i in combinations(a,2)]

The documentation and implementation of the combinations() function can be found on here ...

Update This function should do what you want:

def chose(elements, k):
    output = []
    if k == 1:
        return [[i] for i in elements]
    else:
        for i in range(len(elements)):
            head = elements[i]
            tails = chose(elements[i+1:], k-1)
            output += [[head] + tail for tail in tails]
        return output

print chose(['a','b','c'], 2)

Upvotes: 2

Padraic Cunningham
Padraic Cunningham

Reputation: 180481

You can use a powerset without using any imports:

def power_set(items,k):
    n = len(items)
    for i in xrange(2**n):
        combo = []
        for j in xrange(n):
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        if len(combo) == k:
            yield combo

print(list(power_set(['a', 'b', 'c'],2)))

[['a', 'b'], ['a', 'c'], ['b', 'c']]

Upvotes: 1

Related Questions