python - 一组玩家的所有可能的纸牌/扑克牌组合

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 and d) 等于 (d and c)

我已经尝试了 itertools 的功能，例如 combinations 和 permutations 但没有成功。由于状态空间爆炸，在拥有所有组合后拒绝等于并不是一个真正的选择。

我希望有人有解决方案，因为谷歌搜索这个特定问题失败了。

Answer 1

我建议使用递归算法。

我正在使用生成器让代码在常量空间中运行，并尽快开始产生结果，而不是在最后产生巨大的结果；见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',
...