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

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

我建议使用递归算法。

我使用生成器的代码运行在恒定空间，以及开始尽快产生结果，而不是在最后一个巨大的结果;如果您以前没有听说过生成器，请参阅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',
...

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

您可以使用每个人的卡片数组，并将卡片按顺序排列，因此当您匹配两个数组时，它们将是相同的。您可以为每张卡片使用一个元组(大小为2)，其中第一个元素可以表示范围(13)内的值，第二个元素将表示颜色(也用范围(4)内的数字表示)。你可以很容易地生成甲板的双重循环,也许作为一个字典和处理卡后,您可以删除那些你已经使用,所以不会有重复的,当你处理所有的手(如果你有代码将是容易修改它有不同数量的球员)你可以秩序的手,比较它与数据库,你已经不要保存它如果有比赛,你也可以保存剩下的甲板,如果你想做一些统计，那么你就可以得到每种情况下所有可能的交易，这将是一个巨大的数据库。这样你就有了所有的可能性，没有重复的在手或在玩家的手中。(玩家1的手牌与玩家2的手牌不同，反之亦然)我希望这对你或其他人有所帮助。我没有给出代码示例，因为这个问题更像是如何解决这个问题，其他人给了你编码技巧。而且，即使您刚刚开始学习python，并且到目前为止只学习了一些教程，也可以使用这种方法。祝你好运;)