CODEWITHSUNDEEP
pythongeneratorpermutation
Mil Mil
Mil Mil

Reputation: 33

Naive permutation algorithm that python generator function doesn't support

guys. It seems like I don't really understand the concept of Python generator functions, because I haven't figured out mistake in this code that is supposed to produce all the permutations of the string characters.

For instance, this one is based on simple set expansion and it works 

def permutations(seq):
    perm_set = set()

    def perm(cur_item_set, cur_str=''):
        if not cur_item_set:
            perm_set.add(cur_str)
        else:
            for item in cur_item_set:
                perm(cur_item_set - set(item), cur_str + item)

    perm(set(seq))

    for (i, item) in enumerate(perm_set):
        print(i + 1, item)

    permutations('abcdef')

Meanwhile, this code doesn't work: list(g) provides [] 

def gen_perm(cur_item_set, cur_str=''):
    if not cur_item_set:
        yield cur_str
    else:
        for item in cur_item_set:
            gen_perm(cur_item_set - {item}, cur_str + item)

g = gen_perm(set('abcd'))

Upvotes: 1

Views: 273

Answers (1)

Robᵩ
Robᵩ

Reputation: 168646

When you recursively call gen_perm(), you don't do anything with the return value.

Try this, if yield from is available in your Python version (3.3 and above):

def gen_perm(cur_item_set, cur_str=''):
    if not cur_item_set:
        yield cur_str
    else:
        for item in cur_item_set:
            yield from gen_perm(cur_item_set - {item}, cur_str + item)

g = gen_perm(set('abcd'))
print (list(g))

Or this will work on all Python versions.

def gen_perm(cur_item_set, cur_str=''):
    if not cur_item_set:
        yield cur_str
    else:
        for item in cur_item_set:
            for item2 in gen_perm(cur_item_set - {item}, cur_str + item):
                yield item2

g = gen_perm(set('abcd'))
print (list(g))

Upvotes: 2

Related Questions