Generating all combinations

Steven D'Aprano steven at REMOVE.THIS.cybersource.com.au
Thu Jun 4 05:53:45 CEST 2009

```On Wed, 03 Jun 2009 18:21:37 -0700, Mensanator wrote:

[mass snippage]
> What I *was* talking about is this quote from the 3.1 What's New page:
>
> <quote>
> The itertools.combinations_with_replacement() function is one of four
> for generating combinatorics including permutations and Cartesian
> products.
> </quote>
>
> Is there some reason I *shouldn't* assume that the "four for generating
> combinatorics" are not permutations vs combinations & with vs without
> replacement? Does the fact that product() can do more than operate on a
> single set change that? I never said it couldn't.

Settle down Mensanator! Don't take it so personally! You're sounding
awfully agitated.

The quoted doc doesn't imply that there are only four combinatorics
functions, only that there are four *in itertools*. Nor does it say that
permutations etc are subsets of the Cartesian Product, because *without
clarification* that is a fairly dubious thing to say. Remember, these are
terms with very precise technical meanings, and if you say to a
mathematician "the permutations P of some set S are a subset of the
Cartesian Product with no specified arguments", they'll probably react
just as I did -- with confusion.

Now that I've narrowed down what you actually meant, I'm happy to agree
with you, at least informally.

>> 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:
>
> <snip example>
>
> That *is*, in fact, what I was refering to. I never intended my comment
> to be a complete tutorial on all that can be done with itertools.

Dear me. Did I say it was?

> I was
> that that issue has been addressed. What did I say wrong? Was *I* the
> one who was complaing? (I try not to do that anymore.)

The only thing you did "wrong" was to be less pedantic than me. All I was
trying to do was narrow down in exactly what sense you meant that
arrangements of a single set are subsets of the product of two or more
sets.

>> Oh, there's another type of arrangement missing from the collection...
>> dearrangements.
>
> Is that "one of four for generating combinatorics"?

Obviously not. If it's *missing* how could it be one of the four?

> Maybe you should be talking to the itertools developers?

If I had a good use-case for dearrangements, or a fast, reliable
implementation, then maybe I would.

>> 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?
>
> Ok, but isn't that not within the scope of what we're discussing?

In the context of Pataphor complaining about itertools having an
incomplete set of combinatorics tools, missing partions() and
dearrangements() are certainly within the scope. Whether they are serious
lacks is another question.

--
Steven

```