--=-=-=
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
--=-=-=--
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4