[Tutor] Generating deck combinations

[Paul McGuire]

If you are looking for all possible 60-card deals of this deck, then you
also probably want to filter out duplicate deals caused by equivalent cards
exchanging places.  That is, say you had a deck of 3 cards: 2 Mountain, and
1 Vial, and you want to deal out al 3 in various order of cards.  Using the
recursive solutions, you will get:
    
(hmm, couldn't get either of the previous submissions to work..., well
something like this)

['Mountain', 'Mountain', 'Vial']
['Mountain', 'Vial', 'Mountain']
['Mountain', 'Mountain', 'Vial']
['Mountain', 'Vial', 'Mountain']
['Vial', 'Mountain', 'Mountain']
['Vial', 'Mountain', 'Mountain']


That is, because you have 2 Mountain cards, recursively shuffling this list
*looks* like you have two different list elements to process, but in fact,
they are equivalent so you will get duplicate deals.

Now imagine you have up to 150 different types of cards, in quantities of
1-10 of each, and this problem magnifies considerably.

Try this version (mildly tested):

def deal(cards, size):
    if size > len(cards):
        raise ValueError, "cannot deal more cards than are in the deck"
        
    if size == 1:
        for cd in cards:
            yield [cd]
    else:
        for i,cd in enumerate(cards):
            remainder = cards[:i] + cards[i+1:]
            for d in deal(remainder,size-1):
                yield [cd]+d


cardlist = [('Mountain', 2), ('Vial', 6), ]
allcards = sum(([card,]*qty for card,qty in cardlist), [])

# generate all unique deals of 'n' cards from allcards
# use the seenalready set to avoid reporting duplicate deals
n = 4
seenalready = set()

for d in deal(allcards,n):
    newdeck = tuple(d)
    if newdeck not in seenalready:
        print d
        seenalready.add(newdeck)

Here are all the 4-card deals from this pack of 8 cards:

['Mountain', 'Mountain', 'Vial', 'Vial']
['Mountain', 'Vial', 'Mountain', 'Vial']
['Mountain', 'Vial', 'Vial', 'Mountain']
['Mountain', 'Vial', 'Vial', 'Vial']
['Vial', 'Mountain', 'Mountain', 'Vial']
['Vial', 'Mountain', 'Vial', 'Mountain']
['Vial', 'Mountain', 'Vial', 'Vial']
['Vial', 'Vial', 'Mountain', 'Mountain']
['Vial', 'Vial', 'Mountain', 'Vial']
['Vial', 'Vial', 'Vial', 'Mountain']
['Vial', 'Vial', 'Vial', 'Vial']

(If order is not significant, then you could simplify this algorithm
accordingly, and you would get these results:
['Mountain', 'Mountain', 'Vial', 'Vial']
['Mountain', 'Vial', 'Vial', 'Vial']
['Vial', 'Vial', 'Vial', 'Vial']
)

This is definitely a brute-force approach (brute-force is actually my
favorite first approach), generating all possible deals and then filtering
duplicates using a set of "already been seen" deals.  A smarter algorithm
would generate only the unique deals.  If someone were paying me to be that
smart, maybe I'd work on it.

I'm guessing this is an attempt to optimize a deck for playing a card game
like Magic or Pokemon, etc.  Your plan is, given a set of 'n' cards in your
collection (presumbaly n>60, or there would be no problem to solve), to
compute all possible decks of 60 cards.  Then you have some function to
evaluate this deck, or perhaps simulate playing it against another deck.
You will then exhaustively run this simulation function against each deck to
find which deck from your collection of 100's of cards is the "best".

By the time your program has finished running, I suspect the sun will be a
cold, dark cinder.  But have fun with it.

-- Paul