Print n choose k combination algorithm using recursion

Question

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?

By the way, >>> [''.join(c) for c in combinations(['a','b','c','d'], 2)] ; ['ab', 'ac', 'ad', 'bc', 'bd', 'cd'] — cs95
– cs95, Commented Jul 4, 2017 at 21:34

willeM_ Van Onsem · Accepted Answer · 2017-07-04 21:43:33Z

6

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

edited Jul 4, 2017 at 21:43

answered Jul 4, 2017 at 21:37

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

cs95 Over a year ago

This prints da, db, dc too.

willeM_ Van Onsem Over a year ago

@cᴏʟᴅsᴘᴇᴇᴅ: and that's now fixed :)

aerin Over a year ago

Thank you so much! It's funny to see how fast this uv dv changes according to your edit :)

cs95 Over a year ago

@ToussaintLouverture You should accept this answer because it answers your question. But for a cleaner approach, do take a look at my answer.

CraigDavid Over a year ago

Any idea what the time complexity is here? Nice code @WillemVanOnsem!

cs95 · Accepted Answer · 2017-07-04 22:08:46Z

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']

Collectives™ on Stack Overflow

Print n choose k combination algorithm using recursion

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related