New to Python - Want code review of simple combination routine
John Hunter
jdhunter at nitace.bsd.uchicago.edu
Wed May 22 13:29:45 EDT 2002
>>>>> "Michael" == Michael Bauers <MichaelB at firstlogic.com> writes:
Michael> I am posting a routine I wrote to return a list of
Michael> combinations. The input to 'combination' is a list, and
Michael> 'n' which represents the number of elements to take in
Michael> combination. If you forgot your math, [1,2,3] with n=2
Michael> should give [[1,2], [1,3], [2,3]]
I know this is not exactly what you are asking, but you may be
interested to see how others have solved the problem:
From: http://www.faqts.com/knowledge_base/view.phtml/aid/4526/fid/538
class CombGen:
def __init__(self, seq, k):
n = self.n = len(seq)
if not 1 <= k <= n:
raise ValueError("k must be in 1.." + `n` + ": " + `k`)
self.k = k
self.seq = seq
self.empty = seq[0:0] # an empty sequence of this type
self.indices = range(k)
# Trickery to make the first .get() call work.
self.indices[-1] = self.indices[-1] - 1
def get(self):
n, k, indices = self.n, self.k, self.indices
lasti, limit = k-1, n-1
while lasti >= 0 and indices[lasti] == limit:
lasti = lasti - 1
limit = limit - 1
if lasti < 0:
return None
newroot = indices[lasti] + 1
indices[lasti:] = range(newroot, newroot + k - lasti)
# Build the result.
result = self.empty
seq = self.seq
for i in indices:
# There is no general way to spell "append an element to a
# sequence"; addition requires two sequence arguments.
result = result + seq[i:i+1]
return result
def exhaust(seq, k):
g = CombGen(seq, k).get
while 1:
next = g()
if next is None:
break
print next
if __name__=='main':
exhaust([1, 2, 3, 4], 2)
exhaust([1, 2, 3, 4], 3)
exhaust("1234", 3)
More information about the Python-list
mailing list