Generating all combinations

[Steven D'Aprano]

On Mon, 01 Jun 2009 22:20:16 -0700, Mensanator wrote:

>> Are you sure that permutations and combinations are subsets of the
>> Cartesian Product?
> 
> Sure looks that way (SQL examples):
[snip]
> I couldn't do that if they weren't subsets.

Permutations and combinations are arrangements of a single set. The 
Cartesian product, on the other hand, are the arrangements of multiple 
sets, one item from each set. As a general rule, for arbitrary arguments, 
the items you get from product() aren't even the same size as the items 
you get from permutations():


>>> data = (0, 1, 2)
>>> set(itertools.product(data))
{(2,), (0,), (1,)}
>>> set(itertools.permutations(data))
{(2, 1, 0), (0, 1, 2), (1, 0, 2), (2, 0, 1), (0, 2, 1), (1, 2, 0)}


Perhaps you mean that, in the special case of the Cartesian product of a 
set with itself sufficient times, the permutations and combinations of 
that set are subsets of the product? I could live with that:

>>> S = set(itertools.product(data, data, data))
>>> s = set(itertools.permutations(data))
>>> s.issubset(S)
True
>>> s = set(itertools.combinations(data, 3))
>>> s.issubset(S)
True


Oh, there's another type of arrangement missing from the collection... 
dearrangements. That's the arrangements where every item appears in the 
"wrong" place, i.e. in a position where it *didn't* start off: e.g. given 
(1, 2, 3), the dearrangements are: (2, 3, 1), (3, 1, 2). Typical problem: 
you have N addressed letters and envelopes, but someone has shuffled the 
letters before putting them into the envelopes. How many ways are there 
such that no letter will be delivered to the intended recipient?


-- 
Steven