[Tutor] Generating Deck Combinations

[Andre Engels]

On Sat, Jun 20, 2009 at 9: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.
>
> For example:
>
> List1[0] would be: "Aether Vial"
> List2[0] would be: "4"
>
> List1[1] would be: "Mountain"
> List2[1] would be: "10"
>
> List1[2] would be: "Gempalm Incinerator"
> List2[2] would be: "3"
>
> etc.

In my opinion, that's a very unpythonic way of specifying data - I
would use a dictionary for this kind of information:

maximalQuantity = {"Aether Vial": 4, "Mountain": 10, "Gempalm
Incinerator": 3 ...}

> 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.
> So, from the example, I need to generate decks with '1' Aether Vial' and 59
> other cards in all possible combinations (still within the maximum cap for
> each card), and then I'd need to generate decks with '2' Aether Vial' and 58
> other cards in all possible combinations
> It is vital that I create all combinations and that the maximum quantities
> are never breached.
> I am hoping that the each deck could be output as two lists:
> ListA = ['Cardname1', 'Cardname2', ...]
> ListB = ['1', '2', ...]
> These lists will have exactly 60 members.
> If you have an idea of how to do this, please share it! =) I would be most
> appreciative. I'll be testing all methods for speed because I have very
> large amount of computing to do.

Given that ListB will _always_ be ['1', '2', '3', ..., '60'], I do not
see what its use is...

For this problem I would use recursion. I define a function

possible_decks(listA, listB, number)

its input are the lists listA and listB and the number of cards in the
deck, its output is a list of lists, each of which is ListA (it is
confusing to have the same name for two different objects in your
description...) for some legal deck.

The code would be (untested):

def possible_decks(listA, listB, number):
    if number < 0:
        return [] # trying to put more than 60 cards in the deck
    if number == 0:
        return [[]] # there's exactly one deck of size 0 - the empty deck
    if not listA:
        return [] # out of cards, but the deck is not yet full
    thiselement = listA[0]
    thismaximum = int(listB[0])
    returnvalue = []
    for i in xrange(thismaximum):
         possible_rests_of_deck = possible_decks(listA[1:], listB[1:],
number - i)
         returnvalue += [i*[thiselement] + deck for deck in
possible_rests_of_deck]
    return returnvalue

-- 
André Engels, andreengels at gmail.com