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

François Pinard pinard@iro.umontreal.ca
26 Aug 2002 17:56:22 -0400

```--=-=-=
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.

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
# 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, 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, 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, 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.
"""
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

--=-=-=--

```