CODEWITHSUNDEEP
pythonpython-3.xcombinatorics
mavzolej
mavzolej

Reputation: 200

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

Problem:

What would be the best pythonic way to accomplish this?

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

Upvotes: 1

Views: 168

Answers (3)

Dillon Davis
Dillon Davis

Reputation: 7750

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).

Upvotes: 1

Alexander
Alexander

Reputation: 17335

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')]

Upvotes: 1

Sergey Zaykov
Sergey Zaykov

Reputation: 586

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')
>>>

Upvotes: -1

Related Questions