Python: Recursion

Question

although there's quite a bit of information about recursion on the web, I haven't found anything that I was able to apply to my problem. I am still very new to programming so please excuse me if my question is rather trivial.

Thanks for helping out :)

This is what I want to end up with:

listVariations(listOfItems, numberOfDigits) 

>>> listVariations(['a', 'b', 'c'], 1)
>>> ['a', 'b', 'c'] 

>>> listVariations(['a', 'b', 'c'], 2)
>>> ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

>>> listVariations(['a', 'b', 'c'], 3)
>>> ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

but so far I was only able to come up with a function where I need to specify/know the number of digits in advance. This is ugly and wrong:

list = ['a', 'b', 'c']

def listVariations1(list):
  variations = []
  for i in list:
    variations.append(i)
  return variations

def listVariations2(list):
  variations = []
  for i in list:
    for j in list:
      variations.append(i+j)
  return variations

def listVariations3(list):
  variations = []
  for i in list:
    for j in list:
      for k in list:
        variations.append(i+j+k)
  return variations

oneDigitList = listVariations1(list)
twoDigitList = listVariations2(list)
threeDigitList = listVariations3(list)

This is probably very easy, but I couldn't come up with a good way to concatenate the strings when the function calls itself.

Thanks for your effort :)

You really shouldn't use list as a variable name. It's the constructor for the builtin list class and when you do this, you shadow it. — aaronasterling
– aaronasterling, Commented Nov 26, 2010 at 11:24

Srinivas Reddy Thatiparthy · Accepted Answer · 2010-11-26 11:12:39Z

5

You can use the product() function in itertools

answered Nov 26, 2010 at 11:12

Srinivas Reddy Thatiparthy

11.2k4 gold badges48 silver badges68 bronze badges

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

2 Comments

aaronasterling Over a year ago

list(''.join(item) for item in itertools.product(list_, repeat=3))

TIM Over a year ago

this is exactly what I was looking to achieve. thanks guys :)

jairajs89 · Accepted Answer · 2010-11-26 11:11:18Z

0

from itertools import combinations_with_replacement

This function does exactly what you want.

answered Nov 26, 2010 at 11:11

jairajs89

4,9853 gold badges20 silver badges14 bronze badges

1 Comment

aaronasterling Over a year ago

This only works in python 3.1 or greater. And isn't right anyways. Srinivas Reddy Thatiparth gave the right answer.

satoru · Accepted Answer · 2010-11-26 12:20:21Z

0

You can use itertools.permutations to do this.

from itertools import permutations

def listVariations(listOfItems, numberOfDigits):
    return [''.join(x) for x in permutations(listOfItems, numberOfDigits)]

If you do want to implement something similar with recursive function call, you can do it like this:

def permute(seq, n):
    for i in xrange(len(seq)):
        head, tail = seq[i:i+1], seq[0:i]+seq[i+1:]
        if n == 1: 
            yield head
        else:
            if tail:
                for sub_seq in permute(tail, n-1):
                    yield head + sub_seq
            else:
                yield head

a_list = ['a', 'b', 'c']
list(permute(''.join(a_list), 2))
a_str = 'abc'
list(permute(a_str, 2))

edited Nov 26, 2010 at 12:20

answered Nov 26, 2010 at 11:53

satoru

33.4k35 gold badges100 silver badges151 bronze badges

Collectives™ on Stack Overflow

Python: Recursion

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related