Generating all combinations

[Steven D'Aprano]

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
> replying to pataphor's bitching about the itertools being incomplete,
> 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