"n choose m" module

[John Lehmann]

One day, in a fit of boredom when my newscientist subscription was a
week late and I was reduced to solving the enigma puzzle, I wrote a
class to generate the permutations from a list.  I assume I was wasting
my time and that would have been something in the standard libraries,
but in case anyone finds it useful...
-------------- next part --------------
"""

a class for generating permutations from an array

# choose 2 letters from 'abcd'
c = Chooser(['a', 'b', 'c', 'd'], 2)
while c.hasMoreElements():
	print c.next()

"""
import time, copy

class NoMoreChoices(StandardError):
	pass

class Chooser:
	def __init__(self, l, n):
		" generate permutations of n choices of l "
		if n > len(l):
			raise StandardError("cannot make %d choices from a list %d items long"%(n, len(l)))
		self.l = l
		self.n = n
		self.c = range(n)
		self.dirty = 0
		
	def hasMoreElements(self):
		" determine whether there more elements to generate "
		if self.c == None:
			return false
		if self.dirty:
			self.generatenext()
		return self.c <> None

	def next(self):
		" get the next element "
		if self.dirty:
			self.generatenext()
		self.dirty = 1
		return self.getmap(self.c)

	def getmap(self, c):
		m = []
		for i in c:
			m.append(self.l[i])
		return m
	
	def generatenext(self):
		# from the current choice
		self.dirty = 0
		c = self.c
		n = self.n
		ll = len(self.l)
		done = 0
		i = n - 1
		try:
			while not done:
				# take the last element and increment by 1		
				c[i] = c[i] + 1
				# check for modulo overflow
				while c[i] == ll:
					# carry the 1
					c[i] = 0
					i = i - 1
					c[i] = c[i] + 1
					if i == -1:
						raise NoMoreChoices()
				i = n - 1
				if not self.containsduplicates(c):
					done = 1
			self.c = c
		except NoMoreChoices, e:
			self.c = None

	def containsduplicates(self, c):
		" check for duplicate entries "
		for i in range(self.n):
			if c[i] in c[i + 1:]:
				return 1
		return 0