using python itertools to generate custom iteration

Question

I know by using itertools, we can generate products, permutations and combinations. However, considering a case like:

max_allowed_len(sequence)= 3 
iterable= ABC
repeat= 3 (or just `range(len('ABC')`)

I am interested in generating the all different iterable set of ABC with len(sequence)=0 len(sequence)=1 OR len(sequence)=2 and len(sequence)=3 by having repetitions r. Its kinda of a weird permutation with repetitions allowing different sequences. So my space is: 3^0 + 3^1 + 3^2 + 3^3= 1 + 3 + 9+ 27= 40 Can anyone suggest me how to implement that in python or even c/c++ ?

e.g: expected output:

`'0' (nothing(sequence length 0))

Sequence with length=1

'A'
'B'
'C'

Sequence with length=2

'AA'
'BB'
'CC'
'AB'
'AC',...

Sequence with length=3

'AAB'
'ABA'
'AAC'
'ACA'` 

and this goes on. So here I had length of 0, 1, 2 and 3(maxed).

Answer 1

Here's a (relatively) simple way to construct such an iterator for string input. It outputs an empty string '' for the null sequence. I call it twice to make the output easier to read.

The core of the function is a generator expression loop using product with a repeat arg to generate iterators for each group of products of length from zero up to the input string's length. These iterators are then consumed by chain.from_iterable and fed to the ''.join method, using imap to actually call the method on each tuple that was produced by product.

from itertools import product, chain, imap

def all_prod(s):
    return imap(''.join, chain.from_iterable(product(s, repeat=i) for i in range(len(s)+1)))

print(list(all_prod('ABC')))

for s in all_prod('abc'):
    print(s)

output

['', 'A', 'B', 'C', 'AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC', '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']

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
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

---

FWIW, here's an alternate version that uses the plain chain function; it uses an extra loop instead of imap, so it may be less efficient, but I suppose it's may also be a little easier to understand.

def all_prod(s):
    return (''.join(v) for u in chain(product(s, repeat=i) for i in range(len(s)+1)) for v in u)