Combinations of set elements with replacements, with a maximum number of repetitions

Question

Problem:

I have a list of elements without repetitions (a set, basically);
I would like to have a list of all their combinations of length L containing no more than r repetitions of each element.

What would be the best pythonic way to accomplish this?

Probably some adjustments to this answer could be made?..

score 1 · Answer 1 · answered Oct 03 '22 at 04:40

You can use the itertools.combinations_with_replacement and then filter out the ones with too many repeated elements using the collections.Counter.

from itertools import combinations_with_replacement
from collections import Counter

a = ["h","e","l","o","w","r","d"]
L, r = 3, 2
result = []

for combo in combinations_with_replacement(a, L):
    tally = Counter(combo)
    if max(tally.values()) <= r:
        result.append(combo)

print(result)

OUTPUT

[('h', 'h', 'e'), ('h', 'h', 'l'), ('h', 'h', 'o'), ('h', 'h', 'w'), ('h', 'h', 'r'), ('h', 'h', 'd'), ('h', 'e', 'e'), ('h', 'e', 'l'), ('h', 'e', 'o'), ('h', 'e', 'w'), ('h', 'e', 'r'), ('h', 'e', 'd'),
 ('h', 'l', 'l'), ('h', 'l', 'o'), ('h', 'l', 'w'), ('h', 'l', 'r'), ('h', 'l', 'd'), ('h', 'o', 'o'), ('h', 'o', 'w'), ('h', 'o', 'r'), ('h', 'o', 'd'), ('h', 'w', 'w'), ('h', 'w', 'r'), ('h', 'w', 'd'),
 ('h', 'r', 'r'), ('h', 'r', 'd'), ('h', 'd', 'd'), ('e', 'e', 'l'), ('e', 'e', 'o'), ('e', 'e', 'w'), ('e', 'e', 'r'), ('e', 'e', 'd'), ('e', 'l', 'l'), ('e', 'l', 'o'), ('e', 'l', 'w'), ('e', 'l', 'r'),
 ('e', 'l', 'd'), ('e', 'o', 'o'), ('e', 'o', 'w'), ('e', 'o', 'r'), ('e', 'o', 'd'), ('e', 'w', 'w'), ('e', 'w', 'r'), ('e', 'w', 'd'), ('e', 'r', 'r'), ('e', 'r', 'd'), ('e', 'd', 'd'), ('l', 'l', 'o'),
 ('l', 'l', 'w'), ('l', 'l', 'r'), ('l', 'l', 'd'), ('l', 'o', 'o'), ('l', 'o', 'w'), ('l', 'o', 'r'), ('l', 'o', 'd'), ('l', 'w', 'w'), ('l', 'w', 'r'), ('l', 'w', 'd'), ('l', 'r', 'r'), ('l', 'r', 'd'),
 ('l', 'd', 'd'), ('o', 'o', 'w'), ('o', 'o', 'r'), ('o', 'o', 'd'), ('o', 'w', 'w'), ('o', 'w', 'r'), ('o', 'w', 'd'), ('o', 'r', 'r'), ('o', 'r', 'd'), ('o', 'd', 'd'), ('w', 'w', 'r'), ('w', 'w', 'd'),
 ('w', 'r', 'r'), ('w', 'r', 'd'), ('w', 'd', 'd'), ('r', 'r', 'd'), ('r', 'd', 'd')]

That works, thank you. Wondering how far this solution is from being optimal :) — mavzolej, Oct 03 '22 at 04:58
Count how many items are generated vs how many are accepted if you want to do know "optimal" this is. I suspect the depends on how long the list, how many you're accessing, and what "r" is. — Frank Yellin, Oct 03 '22 at 05:02

score 1 · Answer 2 · answered Oct 15 '22 at 09:15

Here's a custom implementation, that avoids all unnecessary computation:

def comb(elements, size, repeat):
    yield from _comb(elements, size, repeat, ()) 

def _comb(elements, size, repeat, accum):
    if size == 0:
        yield accum
        return

    elem, *rest = elements

    min_count = max(size-repeat*len(rest), 1)
    max_count = min(size, repeat) + 1 
    for count in range(min_count, max_count):
        new_accum = accum + (elem, ) * count
        yield from _comb(rest, size-count, repeat, new_accum)

Example:

>>> list(comb([2,3,4,5], size=7, repeat=3))
[(2, 3, 4, 4, 5, 5, 5), (2, 3, 4, 4, 4, 5, 5), (2, 3, 3, 4, 5, 5, 5), (2, 3, 3, 4, 4, 5, 5), (2, 3, 3, 4, 4, 4, 5), (2, 3, 3, 3, 4, 5, 5), (2, 3, 3, 3, 4, 4, 5), (2, 3, 3, 3, 4, 4, 4), (2, 2, 3, 4, 5, 5, 5), (2, 2, 3, 4, 4, 5, 5), (2, 2, 3, 4, 4, 4, 5), (2, 2, 3, 3, 4, 5, 5), (2, 2, 3, 3, 4, 4, 5), (2, 2, 3, 3, 4, 4, 4), (2, 2, 3, 3, 3, 4, 5), (2, 2, 3, 3, 3, 4, 4), (2, 2, 2, 3, 4, 5, 5), (2, 2, 2, 3, 4, 4, 5), (2, 2, 2, 3, 4, 4, 4), (2, 2, 2, 3, 3, 4, 5), (2, 2, 2, 3, 3, 4, 4), (2, 2, 2, 3, 3, 3, 4)]

You can of course covert this to an iterative variant if you run into issues with recursion depth (if there's too many elements in your list).

score -1 · Answer 3 · answered Oct 03 '22 at 04:35

Look at combinations_with_replacement() in itertools

import itertools
for combination in itertools.combinations_with_replacement(['red', 'green', 'blue', 'yellow'], r=3):
     print(combination)

('red', 'red', 'red')
('red', 'red', 'green')
('red', 'red', 'blue')
('red', 'red', 'yellow')
('red', 'green', 'green')
('red', 'green', 'blue')
('red', 'green', 'yellow')
('red', 'blue', 'blue')
('red', 'blue', 'yellow')
('red', 'yellow', 'yellow')
('green', 'green', 'green')
('green', 'green', 'blue')
('green', 'green', 'yellow')
('green', 'blue', 'blue')
('green', 'blue', 'yellow')
('green', 'yellow', 'yellow')
('blue', 'blue', 'blue')
('blue', 'blue', 'yellow')
('blue', 'yellow', 'yellow')
('yellow', 'yellow', 'yellow')
>>>

Combinations of set elements with replacements, with a maximum number of repetitions

3 Answers3