[Python-Dev] A `cogen' module [was: Re: PEP 218 (sets); moving set.py to Lib]

[François Pinard]

--=-=-=
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit

[François Pinard]

> Allow me some random thoughts.  [...]  Some people may think that these
> are all problems which are orthogonal to the design of a basic set feature,
> and which should be addressed in separate Python modules.

>From the received comments, I wrote a simple module reading sequences and
generating lists, instead of reading and producing sets, and taking care
of generating cartesian products, power sets, combinations, arrangements
and permutations.  I took various ideas here and there, like from previously
published messages on the Python list, and made them to look a bit alike.

The module could be called `cogen', abbreviation for COmbinatorial
GENerators.  Here is a first throw, to be criticised and improved.


--=-=-=
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: attachment; filename=cogen.py
Content-Transfer-Encoding: 8bit

#!/usr/bin/env python
# Copyright © 2002 Progiciels Bourbeau-Pinard inc.
# François Pinard <pinard@iro.umontreal.ca>, 2002-08.

"""\
Combinatorial generators.

All generators below have the property of yielding successive results
in sorted order, given than input sequences were already sorted.
"""

from __future__ import generators

def cartesian(*sequences):
    """\
Generate the `cartesian product' of all SEQUENCES.  Each member of the
product is a list containing an element taken from each original sequence.
"""
    if len(sequences) == 0:
	yield []
    else:
	first, remainder = sequences[0], sequences[1:]
	for element in first:
	    for result in cartesian(*remainder):
		result.insert(0, element)
		yield result

def subsets(sequence):
    """\
Generate all subsets of a given SEQUENCE.  Each subset is delivered
as a list holding zero or more elements of the original sequence.
"""
    yield []
    if len(sequence) > 0:
        first, remainder = sequence[0], sequence[1:]
        # Some subsets retain FIRST.
        for result in subsets(remainder):
            result.insert(0, first)
            yield result
        # Some subsets do not retain FIRST.
        for result in subsets(remainder):
            if len(result) > 0:
                yield result

def combinations(sequence, number):
    """\
Generate all combinations of NUMBER elements from list SEQUENCE.
"""
    # Adapted from Python 2.2 `test/test_generators.py'.
    if number > len(sequence):
	return
    if number == 0:
	yield []
    else:
	first, remainder = sequence[0], sequence[1:]
	# Some combinations retain FIRST.
	for result in combinations(remainder, number-1):
	    result.insert(0, first)
	    yield result
	# Some combinations do not retain FIRST.
	for result in combinations(remainder, number):
	    yield result

def arrangements(sequence, number):
    """\
Generate all arrangements of NUMBER elements from list SEQUENCE.
"""
    # Adapted from PERMUTATIONS below.
    if number > len(sequence):
	return
    if number == 0:
	yield []
    else:
	cut = 0
	for element in sequence:
	    for result in arrangements(sequence[:cut] + sequence[cut+1:],
				       number-1):
		result.insert(0, element)
		yield result
	    cut += 1

def permutations(sequence):
    """\
Generate all permutations from list SEQUENCE.
"""
    # Adapted from Gerhard Häring <gerhard.haering@gmx.de>, 2002-08-24.
    if len(sequence) == 0:
	yield []
    else:
	cut = 0
	for element in sequence:
	    for result in permutations(sequence[:cut] + sequence[cut+1:]):
		result.insert(0, element)
		yield result
	    cut += 1

def test():
    if True:
	print '\nTesting CARTESIAN.'
	for result in cartesian((5, 7), [8, 9], 'abc'):
	    print result
    if True:
        print '\nTesting SUBSETS.'
        for result in subsets(range(1, 5)):
            print result
    if True:
	print '\nTesting COMBINATIONS.'
	sequence = range(1, 5)
	for counter in range(len(sequence) + 2):
	    print "%d-combs of %s:" % (counter, sequence)
	    for combination in combinations(sequence, counter):
		print "   ", combination
    if True:
	print '\nTesting ARRANGEMENTS.'
	sequence = range(1, 5)
	for counter in range(len(sequence) + 2):
	    print "%d-arrs of %s:" % (counter, sequence)
	    for combination in arrangements(sequence, counter):
		print "   ", combination
    if True:
	print '\nTesting PERMUTATIONS.'
	for permutation in permutations(range(1, 5)):
	    print permutation

if __name__ == '__main__':
    test()

--=-=-=
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit


-- 
François Pinard   http://www.iro.umontreal.ca/~pinard

--=-=-=--