[Tutor] Generating Deck Combinations

[Kent Johnson]

On Sat, Jun 20, 2009 at 3:49 AM, Michael Morrissey<gdoghomes at gmail.com> wrote:
> I need to generate all possible deck combinations given two different lists
> as input.
> The Input:
> List 1 has Card names listed inside it.
> List 2 has Maximum Quantities for each Card name.

I generally prefer a list of pairs to paired list. In this case I
would use a single list containing tuples of (card name, max
quantitiy).

> A deck is 60 cards total (no more, no less). I need to loop over these lists
> to generate all possible combinations of 60 card decks which use up to the
> maximum quantity for each card.

This cries out for a recursive solution  - pick a number of the first
card, then create all possible decks containing the remaining cards.
Here is one solution. It uses a generator function, so rather than
returning a list of all solutions, it creates an iterator that yields
solutions.

limits = [('A', 3), ('B', 2), ('C', 4)]

def deck(limits, size):
    # Check for end condition
    if size == 0 or not limits:
        yield []
        return

    # The current card and its limit
    card, cardMax = limits[0]

    # The remaining cards
    rest = limits[1:]

    # For each possible number of the current card
    for i in range(0, min(size, cardMax)+1):
        cards = [card] * i

        # Create all possible decks from the remaining cards
        for remainder in deck(rest, size-i):
            if size-i == len(remainder):
                yield cards + remainder

for d in deck(limits, 5):
    print d


There are probably faster ways but this is straightforward. One
inefficiency in this one is that it generates a lot of short solutions
that are screened out by the "if size-i == len(remainder)"
conditional. This conditional isn't hit until the full recursion is
completed. This could be optimized by creating a list of (card name,
max quantity, max quantity following). I.e. the third element is the
most cards that could be added from the remaining cards. If this is
less than size-i, then there is no need to continue, the deck can't be
completed.

Kent