I'd suggest using a recursive algorithm.
I'm using generators for the code to run in constant-space, as well as start producing results ASAP as opposed to a huge result at the end; see http://www.dabeaz.com/generators/ if you haven't heard of generators before.
As a side note, I'd suggest using a normalized data structure to hold your list of players and hand sizes to start with, so that the line with groupby
wouldn't be necessary at all... And in any case, it's generally a good idea to keep your data normalized by default/most of the time and only use denormalized/flattened forms for example for certain algorithms that might need or run faster with flat structures.
Here's the code; feel free to propose clean-ups/simplifications:
from itertools import combinations, groupby, islice
cards = ["a", "b", "c", "d"]
players = ["1", "1", "2", "2"]
def hand_combinations(players, cards):
# convert ["1", "1", "2", "2"] into [("1", 2), ("2", 2)]
players = list((x, len(list(y))) for x, y in groupby(players))
# sets are faster to operate on in our case
cards = set(cards)
def generate(players, cards):
if not players:
yield []
else:
# pick the first player
player_name, player_hand_size = players[0]
# and then walk over all the possible hands for this player
for player_hand in combinations(cards, player_hand_size):
# for each hand, use the cards that are left to build all the
# possible hands for the rest of the players in this iteration
for tail in generate(players[1:], cards - set(player_hand)):
yield [(player_name, player_hand)] + tail
return generate(players, cards)
# take only the 100 first combinations; otherwise it'll take
# forever with the larger example
combos = islice(hand_combinations(players, cards), 0, 100)
# convert back to the flat structure
flattened = [
' '.join(
player_name + ':' + card
for player_name, player_cards in combo
for card in player_cards
)
for combo in combos
]
from pprint import pprint
pprint(flattened)
Outputs:
['1:a 1:c 2:b 2:d',
'1:a 1:b 2:c 2:d',
'1:a 1:d 2:c 2:b',
'1:c 1:b 2:a 2:d',
'1:c 1:d 2:a 2:b',
'1:b 1:d 2:a 2:c']
or with the larger examople:
['_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:8D _To:AH _To:9S _To:10D _Tc:8S',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:8D _To:AH _To:9S _To:8S _Tc:10D',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:8D _To:AH _To:10D _To:8S _Tc:9S',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:8D _To:9S _To:10D _To:8S _Tc:AH',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:10D _To:AH _To:9S _To:8D _Tc:8S',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:10D _To:AH _To:9S _To:8S _Tc:8D',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:10D _To:AH _To:8D _To:8S _Tc:9S',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:10D _To:9S _To:8D _To:8S _Tc:AH',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:AH _To:8S _To:9S _To:10D _Tc:8D',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:AH _To:8S _To:9S _To:8D _Tc:10D',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:AH _To:8S _To:10D _To:8D _Tc:9S',
'_1:AS _1:9H _1:8H _2:AC _2:10H _2:AD _3:10S _3:10C _3:9C _4:8C _4:9D _4:AH _To:9S _To:10D _To:8D _Tc:8S',
...