1

I want to create a list of all words with a certain length (for example 1 to 3) that consist of two letters. So my output would be: a, b, aa, ab, ba, bb,.... but I am struggling to implement it recursively in python. What’s the right way to do this?

T-bone
  • 11
  • 1
  • 1
    Welcome to SO. Noone will code for you here but, instead, help you when struggling. Can you post a code example? What have you tried so far? – Jonathan Oct 09 '19 at 21:00
  • a, b have only one letter – Mykola Zotko Oct 09 '19 at 21:00
  • This can be done non-recursively, do you really have to use a recursive solution? – Thierry Lathuille Oct 09 '19 at 21:02
  • Exactly this is my problem. I have no clue how I should start with it. I‘m not expecting someone to code it for me, but something like a guideline or rough summary would already help me a lot :) – T-bone Oct 09 '19 at 21:04
  • And no I don‘t have to do it recursively but I want to do it for practicing – T-bone Oct 09 '19 at 21:05
  • Please provide a [mcve] including sample input, sample output, and code for what you've tried based on your own research, if any – G. Anderson Oct 09 '19 at 21:08
  • 1
    In Python, recursion is typically not the ideal solution (although it certainly has its place). Instead, Python focuses more heavily on iteration. Take a look a the [itertools](https://docs.python.org/3/library/itertools.html) module, you should find the answer there. – b_c Oct 09 '19 at 21:12
  • Okay, I think product() seems to be the right one – T-bone Oct 09 '19 at 21:29

2 Answers2

1

I combined both itertools and recursion in the following code:

from itertools import product,chain

ab = ['a', 'b']

def rec_prod(x):
    if x==1:
        return ab
    elif x==2:
        return list(product(ab, ab))
    else:
        return [tuple(chain((i[0],), i[1])) for i in product(ab, rec_prod(x-1))]

prod_range = lambda y: list(chain.from_iterable(rec_prod(j) for j in range(1, y+1)))

The first fuction recursively calculates all "words" of length x, the second one returns all words from length 1 to length y. It's a bit messy and not very efficient, but if you study the way I used recursion and the itertools function I used (product and chain) I'm sure you will learn something useful out of it.

Michele Bastione
  • 363
  • 3
  • 13
0

I believe you can use itertools for this, and it is a more pythonic way of approaching the problem. 

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

import itertools
for letter in itertools.permutations(list):
      list.append(' ',join(letter))

this will give you :

list = ['a', 'b', 'c', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Python recursion permutations

This might also help you.

r4bb1t
  • 1,033
  • 2
  • 13
  • 36