CODEWITHSUNDEEP
pythonalgorithmlistrecursioncombinations
snehoozle
snehoozle

Reputation: 273

Recursively Generating a List of n choose k combinations in Python - BUT return a list

I'm attempting to generate all n choose k combinations of a list (not checking for uniqueness) recursively by following the strategy of either include or not include an element for each recursive call. I can definitely print out the combinations but I for the life of me cannot figure out how to return the correct list in Python. Here are some attempts below: 

class getCombinationsClass:

    def __init__(self,array,k):

        #initialize empty array
        self.new_array = []
        for i in xrange(k):
            self.new_array.append(0)

        self.final = []

        self.combinationUtil(array,0,self.new_array,0,k)

    def combinationUtil(self,array,array_index,current_combo, current_combo_index,k):

        if current_combo_index == k:
            self.final.append(current_combo)
            return

        if array_index >= len(array):
            return

        current_combo[current_combo_index] = array[array_index]

        #if current item included
        self.combinationUtil(array,array_index+1,current_combo,current_combo_index+1,k)

        #if current item not included
        self.combinationUtil(array,array_index+1,current_combo,current_combo_index,k)

In the above example I tried to append the result to an external list which didn't seem to work. I also tried implementing this by recursively constructing a list which is finally returned: 

def getCombinations(array,k):

    #initialize empty array
    new_array = []
    for i in xrange(k):
        new_array.append(0)

    return getCombinationsUtil(array,0,new_array,0,k)

def getCombinationsUtil(array,array_index,current_combo, current_combo_index,k):

    if current_combo_index == k:
        return [current_combo]

    if array_index >= len(array):
        return []

    current_combo[current_combo_index] = array[array_index]

    #if current item included & not included
    return getCombinationsUtil(array,array_index+1,current_combo,current_combo_index+1,k) + getCombinationsUtil(array,array_index+1,current_combo,current_combo_index,k)

When I tested this out for the list [1,2,3] and k = 2, for both implementations, I kept getting back the result [[3,3],[3,3],[3,3]]. However, if I actually print out the 'current_combo' variable within the inner (current_combo_index == k) if statement, the correct combinations print out. What gives? I am misunderstanding something to do with variable scope or Python lists?

Upvotes: 2

Views: 7701

Answers (2)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

The second method goes wrong because the line

return [current_combo]

returns a reference to current_combo. At the end of the program, all the combinations returned are references to the same current_combo.

You can fix this by making a copy of the current_combo by changing the line to:

return [current_combo[:]]

The first method fails for the same reason, you need to change:

self.final.append(current_combo)

to

self.final.append(current_combo[:])

Upvotes: 3

fodma1
fodma1

Reputation: 3535

Check this out: itertools.combinations. You can take a look at the implementation as well.

Upvotes: 2

Related Questions