Python 3 exercise: generating permutation

Question

I am trying to write a generator function for permutation for practice. But it does not return anything. But if I replace ´´yield new[k]´´ with ´´lis.append(new[k])´´, then I get the correct list of permutations. Am I doing something wrong with yield?

tup=(1,2,3) # tup can be any sequence
new=[[]]*(len(tup)+1) # memory; new[0]=[], new[1] will be length 1 permutation, etc.
lis=[]  # the list of permutations

def repeat(k): # recursion
    for i in tup:
        if i in new[k-1]:
            continue # permutation can't repeat
        else: new[k]=new[k-1]+[i]

        if k==len(tup): 
             yield new[k]
        else:
             repeat(k+1)

gen=repeat(1)
for i in gen:
    print(i)

They break the formatting. They can only be used with much care, and it's not worth it. Never have a tab in a source file, ever. If you need to put a tab in some text, write it like `'\t'` — Lennart Regebro, Jun 26 '12 at 10:24

score 0 · Answer 1 · edited May 23 '17 at 10:09

0

I think you are trying to write an algorithm for generating permutations of multiple lengths using generators for practice.

Try this question on for size: How to generate all permutations of a list in Python

You'll need to translate to python3, which shouldn't be that big an issue.

Unfortunately, I think your problem lies in your algorithm, rather than your use of yield, which looks okay to me.

edited May 23 '17 at 10:09

Community

1
1

answered Jun 26 '12 at 02:33

Prashant Kumar

20,069
14
47
63

I am storing permutation of shorter length because after generating one full length permutation, I just want to increment the last entry(s) to generate a new full length permutation – user1470575 Jun 26 '12 at 08:39

score 0 · Accepted Answer · answered Jun 26 '12 at 04:50

This is a recursive function, but you don't pass on the value from the recursion, which is why it doesn't return anything.

You need to change the call to

repeat(k+1)

to

for x in repeat(k+1):
    yield x

The resulting function is then:

tup=(1,2,3) # tup can be any sequence
new=[[]]*(len(tup)+1) # memory; new[0]=[], new[1] will be length 1 permutation, etc.
lis=[]  # the list of permutations

def repeat(k): # recursion
    for i in tup:
        if i in new[k-1]:
            continue # permutation can't repeat
        else: new[k]=new[k-1]+[i]

        if k==len(tup): 
             yield new[k]
        else:
             for x in repeat(k+1):
                 yield x

for i in repeat(1):
    print(i)

Which works.

The next step is then to get rid of the global variables.

Thank you. By getting rid of the global variables, do you mean defining another function like permutation(tup) and enclose those variables inside the definition of this function? — user1470575, Jun 26 '12 at 08:36
@user1470575: Well, I mean enclose the variables inside the existing `repeat()` function. But that's not always the correct solution, but another wrapper function is rarely correct. Sometimes a class is a good solution. — Lennart Regebro, Jun 26 '12 at 10:22

Python 3 exercise: generating permutation

2 Answers2