Generating all combinations
mensanator at aol.com
Thu Jun 4 03:21:37 CEST 2009
On Jun 3, 6:57 pm, Steven D'Aprano <st... at REMOVE-THIS-
> 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):
> > I couldn't do that if they weren't subsets.
> Permutations and combinations are arrangements of a single set.
The OP *did* say combinations, didn't he? So the thread *was* in the
context of a single set, wasn't it?
> Cartesian product, on the other hand, are the arrangements of multiple
> sets, one item from each set.
And the Cartesian Product of a set with itself gives you
permutations with replacement.
> 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():
But I wasn't talking about that case.
What I *was* talking about is this quote from the 3.1 What's New page:
The itertools.combinations_with_replacement() function is one of
four for generating combinatorics including permutations and
Is there some reason I *shouldn't* assume that the "four for
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.
> 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:
That *is*, in fact, what I was refering to. I never intended my
to be a complete tutorial on all that can be done with itertools. I
replying to pataphor's bitching about the itertools being incomplete,
that that issue has been addressed. What did I say wrong? Was *I* the
who was complaing? (I try not to do that anymore.)
> Oh, there's another type of arrangement missing from the collection...
Is that "one of four for generating combinatorics"?
Maybe you should be talking to the itertools developers?
> 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?
More information about the Python-list