一组玩家的所有可能卡牌/扑克手牌组合

Question

我在寻找一个优雅（快速）的Python函数，能够生成以下两个数组的所有组合。

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"]

组合的样子会是这样的：

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

但是！不能有重复的组合，我的意思是这样的。

举个例子：

如果牌是：

["a", "b", "c", "d"]

如果玩家是：

["1", "1", "2", "2"]

结果会是：

[1a, 1b, 2c, 2d]
[1a, 1c, 2b, 2d]
[1a, 1d, 2b, 2c]
[1b, 1c, 2a, 2d]
[1b, 1d, 2a, 2c]
[1c, 1d, 2a, 2b]

而不是，比如：

[1a, 1b, 2d, 2c]

玩家2拥有（c和d）和（d和c）是一样的。

我尝试过使用itertools中的一些函数，比如combinations和permutations，但都没有成功。在得到所有组合后再去排除重复的组合并不是一个好办法，因为这样会导致状态空间爆炸。

我希望有人能提供解决方案，因为在谷歌上搜索这个具体问题没有找到结果。

Answer 1

你可以为每个人准备一组牌，把这些牌排好顺序，这样当你把两个数组进行匹配时，它们就会是一样的。
你可以用一个包含两个元素的元组来表示每一张牌，第一个元素可以表示牌的点数（范围是0到12），第二个元素可以表示牌的花色（用数字表示，范围是0到3）。
你可以用两个循环轻松生成一副牌，可能可以用字典来存储。发牌后，你可以把已经用过的牌移除，这样就不会有重复的牌了。当你发完所有的牌（如果你有代码的话，修改成不同数量的玩家会很简单），你可以对这些牌进行排序，和你已有的数据库进行比较，如果有重复的就不保存。同时，你也可以保存剩下的牌，以便做一些统计，这样你就能得到每种情况的所有可能发牌组合，这将是一个庞大的数据库。
通过这种方式，你可以确保所有的可能性都被考虑到，且玩家手中的牌不会重复（比如玩家一的牌不会在玩家二的手中出现，反之亦然）。
希望这对你或其他人有所帮助。
我没有提供代码示例，因为这个问题更像是如何解决这个问题，其他人已经给了你一些编码建议。即使你刚开始学习Python，做了一些教程，这种方法也是可以实现的。
祝你好运；)

Answer 2

好的，实际上你想要的是：

set(tuple(zip(p, players)) for p in it.permutations(cards))

但是这样做花费的时间太长了。所以我们来试试。

cards = set(["8H", "8S", "8C", "8D", "9H", "9S", "9C", "9D", "10H", "10S", "10C", "10D", "AH", "AS", "AC", "AD"])

def deals(cards, players, cards_per_player):
    if not cards:
        yield []
        return
    for hand in it.combinations(cards, cards_per_player[0]):
        hand = set(hand)
        for deal in deals(cards - hand, players[1:], cards_per_player[1:]):
            yield zip([players[0]]*len(hand), hand) + deal

> for deal in deals(cards, ['_1', '_2', '_3', '_4', '_Tc', '_To'], [3,3,3,3,1,3]):
      print deal

虽然这样还是需要很长时间，但有很多种发牌的方法。

Answer 3

我建议使用递归算法。

我在代码中使用生成器，这样可以让程序在占用固定空间的情况下运行，并且能尽快开始输出结果，而不是等到最后才给出一个庞大的结果。如果你之前没听说过生成器，可以看看这个链接：http://www.dabeaz.com/generators/。

另外，我建议一开始就使用一种规范化的数据结构来存储玩家和手牌的列表，这样就不需要用到 groupby 这一行了……总的来说，保持数据的规范化是个好主意，通常情况下都应该这样做，只有在某些算法需要或者在扁平结构下运行更快时，才使用非规范化或扁平化的形式。

下面是代码；欢迎提出改进或简化的建议：

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)

输出：

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

或者用更大的例子：

['_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',
...