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