automatic "lotjes trekken"

[Tim Peters]

[François Pinard, in a galaxy long, long ago]
> By the way, I do not remember any standard library helper to enumerate
> all permutations (or combinations, or arrangements) of a given list
> (or tuple).  Ideally one at a time, of course.  Would this be useful?

[Tim, equally long ago]
> I've likely got all the most useful algorithms coded up already
> (from permutations of n things taken k at a time, to partitions of an
> integer, in lexicographic or "Grey code" orderings).

[François, in present-day Utopia]
> Hello, Tim.  Re-reading this old email of yours.  Copy to Python list,
> in case there is interest to some readers.
>
> What do you call "partitions of an integer"?

It would have been easier to answer this when it was fresh, but what's 100
years among friends <wink>.  The partitions of an integer n > 0 are all the
ways of writing n as a sum of positive integers > 0, without regard to
order.  So, e.g., there are 7 partitions of 5:

    5
    4 + 1
    3 + 2
    3 + 1 + 1
    2 + 2 + 1
    2 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

> How should I read the last "or" above?

Exclusively.  The lexicographic ordering of [1, 2, 3, 4] taken two at a time
is

    [1, 2]
    [1, 3]
    [1, 4]
    [2, 3]
    [2, 4]
    [3, 4]

One of possible Gray code ordering is

    [1, 2]
    [2, 4]
    [2, 3]
    [3, 4]
    [1, 4]
    [1, 3]

The relation to Gray codes is that only one element changes from one line to
the next.  If you're computing a function on these objects as they're
generated, that can save an enormous amount of computation (you only need to
account for that one element went away and that another was added, and a
useful Gray code generator returns those two elements as well as the next
object).  For more, see, e.g.,

    "Loopless Gray Code Algorithms"
    T.A. Jenkyns
    <http://www.cosc.brocku.ca/Department/Research/tech.php3>

Jenkyns has better (simpler, faster) algorithms for this than the far
better-known algorithms in Nijenhuis & Wilf's "Combinatorial Algorithms".


>> There is a particular irritation inherent in your natural generalization
>> from list to "list (or tuple)": you should really add "(or sequence)",
>> including strings and user-defined sequence types.  A polymorphic
>> generator has to be written very carefully to work with all those types!
>> It also has to be written inefficiently, since it can't assume the base
>> sequence type is mutable.  [...]

> Indeed.  I never noticed that as a difficulty before, because the
> application usually knows what to expect, and could convert the result of
> a combinator received as a list, back to a tuple, or string, or whatever.
> As you underline, this allows the combinator routine to be written more
> efficiently, indeed.

In real life I tended to write an xyzGenBasic class that worked solely on
canonical lists of ints in range(n), then built an xyzGen class on top of
that, using the basic class to generate lists of indices.  I got tired of
this, though, since in practice I only *used* the Basic class <0.9 wink>.

>> Another irritation is that the for/__getitem__ protocol isn't really
>> suited to this kind of application

> I do not quote your examples here, as you published elegant solutions
> based on generators since then.  That irritation is gone by now! :-)

Indeed it is!  If I can ever find the old code, I'd rework it to exploit
that.  Curiously, the lack of generators at the time drove me to find
efficient iterative algorithms, and in particular to find the wonderful
paper referenced above.  Nothing is pure win or pure loss <wink>.