[Tutor] Generating Deck Combinations

[Dave Angel]

<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>