Printing all possible combinations using recursion

Question

I'm trying to write a Python program that outputs all possible strings formed by using the characters c, a, t, d, o and g exactly once using recursion only.

so far I've got this:

i = ['c', 'a', 't', 'd', 'o', 'g']

counter = 0
def func(i):

    global counter

    i[counter], i[counter+1] = i[counter+1], i[counter]
    print(i)

    if counter != 5:
        counter += 1
        return func(i)

func(i)

EDIT: sorry for being "impolite", but I just copy-pasted the exercise from the book. This is just a pure text from the book.

@m.wasowski And what are the "combinations"? Name at least two. — Stefan Pochmann, May 17 '15 at 00:32
Tip: algorithm for generating combinations is recursive, it might be easier for you to write it first using recursion. It is not very practical solution in Python,though, but later you might easily rewrite it into iterations. — m.wasowski, May 17 '15 at 00:33
I see you _need _ to use recursion,so start with all combinations of one-element list as the base case, and then think how to construct from this combinations of 2-el list etc. — m.wasowski, May 17 '15 at 00:43
@PaulRooney Also, there is only one "combination" that uses every letter exactly once, so that would be rather boring :-P — Stefan Pochmann, May 17 '15 at 00:58

Stefan Pochmann · Accepted Answer · 2015-05-17T01:15:38.877

6

No idea what you're trying with yours or how to fix that, sorry. But here's one way to do it.

def words(letters, word=''):
    letters or print(word)
    for letter in letters:
        words(letters - {letter}, word + letter)

words(set('catdog'))

The letters or print(word) is just a shortcut for if not letters: print(word). Python's or evaluates the left part, and if that's "truthy", it returns that, otherwise returns the right part. So here, if letters is truthy, i.e., there are letters left to use, then that's it. Otherwise, print.

It's a bit tricky, maybe, but I find it fairly natural. You've maybe heard the phrase "Stop or I'll shoot!", right? If the person stops, then that's it. Otherwise, they'll be shot. Same thing in Python, pretty much.

edited May 17 '15 at 01:15

answered May 17 '15 at 00:26

Stefan Pochmann

27,593
8
44
107

Thank you very much. Could you explain step by step how your code works? I'm confused with this line `letters or print(word)`. – trollpidor May 17 '15 at 01:09
I've added an explanation to the answer. – Stefan Pochmann May 17 '15 at 01:15
I still don't understand the code. In you `for` statement after 1st iteration it returns a function `words({'a', 't', 'd', 'o', 'g'}, word='c')`.It does not print `word` because `letters = True`. But then, after all iterations we get `words({}, word = 'catdog')`, which prints this word because `letters = False`. How is this function able to start 2nd series of iteration and print characters in random order? and why does it get random? – trollpidor May 17 '15 at 01:28
It's random because I use a set to hold the remaining letters, which is useful here. Don't know why you're wondering about 2nd series. After the first, the recursive calls return and others are made. – Stefan Pochmann May 17 '15 at 01:35
eh, still don't understand. Ok, I probably will be able to understand it when I get more experience. Thank you anyway – trollpidor May 17 '15 at 01:42
Yeah, I get the feeling you should maybe try easier recursive functions first. This one is not hard, but there are easier ones. – Stefan Pochmann May 17 '15 at 01:49

score 0 · Answer 2 · edited May 23 '17 at 12:14

0

This page has some good methods (I'm assuming you can't use the itertools module, so just ignore those posts).

StackOverflow Question 104420

edited May 23 '17 at 12:14

Community

1
1

answered May 17 '15 at 00:22

Abd Azrad

301
2
10

Printing all possible combinations using recursion

2 Answers2