[Tutor] Generating Deck Combinations
Dave Angel
davea at ieee.org
Sat Jun 20 15:27:59 CEST 2009
<homework alert>
Michael Morrissey 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.
>
>
> 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.
>
It isn't considered polite to submit questions without even attempting
your own solutions. And classroom assignments should be solved by the
student. But I can give you some general hints.
Since you're doing combinations, not permutations, the usual approach of
making a complete deck (containing all possible duplicates of cards),
and doing selection without replacement won't run in practical time.
Consider writing a generator function (look up yield) that uses
recursion to list all the cases. Worst case recursion would be 59, of
course.
Consider returning the results front loaded:
Aether Vial-4, Mountain-10, ...
....
Aether Vial-4, Mountain-9, ...
....
Aether Vial-4, Mountain-8, ...
....
.........
Aether Vial-3, Mountain-10, ...
That way, the funny edge-cases are at the end, and you can just return
the first time your recursion gets beyond the end of the ListA
While initial testing, pick a much smaller number than 60, like 6. And
of course use smaller numbers for ListB
</homework alert>
More information about the Tutor
mailing list