Generating all combinations

Mensanator 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-
cybersource.com.au> wrote:
> 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 OP *did* say combinations, didn't he? So the thread *was* in the
context of a single set, wasn't it?

> The
> 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():

<snip example>

But I wasn't talking about that case.

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.

>
> 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. 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.)

>
> Oh, there's another type of arrangement missing from the collection...
> dearrangements.

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?

>
> --
> Steven




More information about the Python-list mailing list