CODEWITHSUNDEEP
pythonalgorithmrecursioncombinations
aerin
aerin

Reputation: 22694

Print n choose k combination algorithm using recursion

This must be a classic interview question, however, I'm having a problem understanding it.

Below is my implementation in Python and if you run it, it's only printing ab, ac, ad. It doesn't go to the 'b' (bc, bd) level. 

def Print_nCk (the_list, k, str_builder, used):
    if len(str_builder) == k:
        print str_builder
        return 
    else:
        for i in xrange(len(the_list)):
            if used[i] !=True:
                str_builder+=the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used)
                str_builder = str_builder[:-1]


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

The right answer is ab,ac,ad,bc,bd,cd when above line is passed.

I know the right implementation from here without using used param (http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/) but my question is what is wrong is my implementation?

Can you shed some light on it?

To debug, I printed out "used" every time. The used param becomes (True, True, True, True) after printing "ad" then it doesn't go deeper than that. What's the smart way to fix the used, if I insist on using used?

Upvotes: 2

Views: 1401

Answers (2)

cs95
cs95

Reputation: 402844

Bit late to the party, but I think you should take more advantage of recursion. There's no need to pass any superfluous arguments.

Here's a simpler approach:

def Print_nCk(the_list, size):
    combs = []
    if size == 1: # the base case
        return the_list

    for i, c in enumerate(the_list[:-size + 1]):
        for sub_comb in Print_nCk(the_list[i + 1:], size  - 1): # generate and return all sub-combos of size - 1
            combs.append(c + sub_comb) # for each sub-combo, add the sizeth (or n - sizeth) character

    return combs

This approach generates combinations of size - 1 and combines them with the sizeth character.

For size-2 combinations:

>>> Print_nCk(['a','b','c','d'], 2)
['ab', 'ac', 'ad', 'bc', 'bd', 'cd']

For size-3 combinations:

>>> Print_nCk(['a','b','c','d'], 3)
['abc', 'abd', 'acd', 'bcd']

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477210

You forgot to unset used[i] when you backtrack:

def Print_nCk (the_list, k, str_builder, used):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(len(the_list)):
            if used[i] != True:
                str_builder += the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used)
                str_builder = str_builder[:-1]
                used[i] = False


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

In your current implementation, you set used[i] to True from the moment you pick the i as value. If however later, you decide to pick another branch, you should do the bookkeeping correctly and thus unset the used[i].

Note that now "ab" and "ba" will be generated. You thus generate combinations with symmetry. If you do not want that, you can use an additional parameter. That makes sure that you do not use an index lower than the previously picked one:

def Print_nCk (the_list, k, str_builder, used, prev = 0):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(prev,len(the_list)):
            if used[i] != True:
                str_builder += the_list[i]
                used[i] = True
                Print_nCk(the_list, k, str_builder, used, i+1)
                str_builder = str_builder[:-1]
                used[i] = False


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

Nevertheless, this more or less defeats the purpose of using a "used" array. You can simply use the prev:

def Print_nCk (the_list, k, str_builder, prev = 0):
    if len(str_builder) == k:
        print str_builder
        return
    else:
        for i in xrange(prev,len(the_list)):
            str_builder += the_list[i]
            Print_nCk(the_list, k, str_builder, i+1)
            str_builder = str_builder[:-1]


Print_nCk(['a','b','c','d'], 2, "")

This then prints:

>>> Print_nCk(['a','b','c','d'], 2, "")
ab
ac
ad
bc
bd
cd

Upvotes: 6

Related Questions