# Generating all combinations

Steven D'Aprano steve at REMOVE-THIS-cybersource.com.au
Thu Jun 4 01:57:06 CEST 2009

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

```