I am looking for an elegant(fast) python function that produces every combination from the following two arrays.
cards = ["8H", "8S", "8C", "8D", "9H", "9S", "9C", "9D", "10H", "10S", "10C", "10D", "AH", "AS", "AC", "AD"]
players = ["_1", "_1", "_1", "_2", "_2", "_2", "_3", "_3", "_3", "_4", "_4", "_4", "_To", "_To", "_To", "_Tc"]
A combination would look like:
[('8H', '_1'), ('8S', '_1'), ('8C', '_1'), ('8D', '_2'), ('9H', '_2'), ('9S', '_2'), ('9C', '_3'), ('9D', '_3'), ('10H', '_3'), ('10S', '_4'), ('10C', '_4'), ('10D', '_4'), ('AH', '_To'), ('AS', '_To'), ('AC', '_To'), ('AD', '_Tc')]
But! without equals, what I mean with that. Example:
If cards would be:
["a", "b", "c", "d"]
If players would be:
["1", "1", "2", "2"]
Result:
[1a, 1b, 2c, 2d]
[1a, 1c, 2b, 2d]
[1a, 1d, 2b, 2c]
[1b, 1c, 2a, 2d]
[1b, 1d, 2a, 2c]
[1c, 1d, 2a, 2b]
Not for example:
[1a, 1b, 2d, 2c]
Player 2 having (c and d) is equal to (d and c)
I have tried a function of itertools, like combinations and permutations but without luck. Rejecting equals after having all combinations is not really an option, because of the state space explosion.
I hope someone has a solution, because google search for this specific problem failed.
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',
...