n choose k

n_choose_k.py

def C(S,k):
    '''Choose k elements from set S.'''
    assert len(S) >= k
    if k==0:
        yield set()
    S1 = S.copy()
    for s in S:
        S1.remove(s)
        if len(S1) >= k-1:
            for c in C(S1, k-1):
                yield set([s]) | c

for c in C(set('abcd'), 0):
    print ''.join(c)

The problem with revision 785674 is that the argument S gets changed (removing elements from it) by all levels of recursions. Since S is passed by reference, it's changed by a deeper level of recursion unintentionally.

def caller(lst):
    print "before calling callee:", lst
    callee(lst)
    print "after  calling callee:", lst

def callee(lst):
    del lst[-1]

caller([1,2,3])