Python itertools generating a powerset with replacements

Question

I'm trying to generate a powerset of a large list of strings that includes replacements. None of the built-in itertools functions do this (as far as I can tell).

EDIT Maybe using "set" in the title was misleading. Order is important here. 'ca' != 'ac'

Example of what I want:

print( powerset_with_replacement(['abc']) )
# yeilds
('a',)
('b',)
('c',)
('a', 'a')
('a', 'b')
('a', 'c')
('b', 'b')
('b', 'c')
('c', 'c')
('a', 'a', 'a')
('a', 'a', 'b')
('a', 'a', 'c')
('a', 'b', 'b')
('a', 'b', 'c')
('a', 'c', 'c')
('b', 'b', 'b')
('b', 'b', 'c')
('b', 'c', 'c')
('c', 'c', 'c')

I got this far already but it seems messy.. I'm wondering if there is a cleaner or more pythonic way to do this. Any help is much appreciated.

Is there a way to get rid of the flatten function or put that inside the main one?

from itertools import combinations_with_replacement
import collections

def flatten(it):
    for x in it:
        if (isinstance(x, collections.abc.Iterable) and
            not isinstance(x, tuple)):
            yield from flatten(x)
        else:
            yield x

def powerset_with_replacement(list1):
   for i in range(1,len(list1)+1):
      yield( combinations_with_replacement(list1, i) )

y = flatten(powerset_with_replacement(list('abc')))

for x in y:
    print(x)

This may be a more graceful way of doing it: https://stackoverflow.com/questions/51538192/getting-all-combinations-of-a-string-and-its-substrings — sd_0912, Sep 16 '19 at 02:56
I don't think any of those have replacement though. Notice how 'aa' and 'aaa' are in my output. — vopsea, Sep 16 '19 at 04:06

Trevor · Answer 1 · 2021-10-19T22:37:49.737

Create a list of cartesian products of size 1 to len(X)

from itertools import product, chain

x = 'abc'
prods = chain.from_iterable(product(x,repeat=n) for n in range(1,len(x)+1))
[print(_) for _ in prods]

Output

('a',)
('b',)
('c',)
('a', 'a')
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'b')
('b', 'c')
('c', 'a')
('c', 'b')
('c', 'c')
('a', 'a', 'a')
('a', 'a', 'b')
('a', 'a', 'c')
('a', 'b', 'a')
('a', 'b', 'b')
('a', 'b', 'c')
('a', 'c', 'a')
('a', 'c', 'b')
('a', 'c', 'c')
('b', 'a', 'a')
('b', 'a', 'b')
('b', 'a', 'c')
('b', 'b', 'a')
('b', 'b', 'b')
('b', 'b', 'c')
('b', 'c', 'a')
('b', 'c', 'b')
('b', 'c', 'c')
('c', 'a', 'a')
('c', 'a', 'b')
('c', 'a', 'c')
('c', 'b', 'a')
('c', 'b', 'b')
('c', 'b', 'c')
('c', 'c', 'a')
('c', 'c', 'b')
('c', 'c', 'c')

score 0 · Answer 2 · answered Oct 19 '21 at 21:59

You can define your own generator and mix in itertools.product to achieve this result:

def combinations_upto(x):
    for i in range(len(x)):
        yield from itertools.product(x, repeat=i+1)

x = "abc"
combo_list = list(combinations_upto(x))
print(combo_list)

Python itertools generating a powerset with replacements

2 Answers2

Output