[Numpy-discussion] how do I list all combinations

Timothy Hochberg tim.hochberg@ieee....
Wed Dec 26 16:48:18 CST 2007


Here's a baroque way to do it using generated code:

    def cg_combinations(seqs):
        n = len(seqs)
        chunks = ["def f(%s):" % ', '.join('s%s' % i for i in range(n))]
        for i in reversed(range(n)):
            chunks.append(" " * (n -i) + "for x%s in s%s:" % (i, i))
        chunks.append(" " * n + " yield (" + ', '.join('x%s' % i for i in
range(n)) + ')')
        code = '\n'.join(chunks)
        exec code
        return f(*seqs)

It should be reasonably fast, if non-obvious. I've included a version with
some timing and testing against Chucks version below. Enjoy.

(Also, it can be simplified slightly, but I wanted to generate in the same
order as Chuck for comparison purposes).


======================================================================


    def count(seqs) :
        counter = [0 for i in seqs]
        maxdigit = [len(i) - 1 for i in seqs]
        yield counter
        while True :
            i = 0;
            while i < len(counter) and counter[i] >= maxdigit[i] :
                counter[i] = 0
                i += 1
            if i < len(counter) :
                counter[i] += 1
                yield counter
            else :
                return

    def count_combinations(seqs):
        for c in count(seqs):
            yield tuple(s[i] for (s, i) in zip(seqs, c))

    def cg_combinations(seqs):
        n = len(seqs)
        chunks = ["def f(%s):" % ', '.join('s%s' % i for i in range(n))]
        for i in reversed(range(n)):
            chunks.append(" " * (n -i) + "for x%s in s%s:" % (i, i))
        chunks.append(" " * n + " yield (" + ', '.join('x%s' % i for i in
range(n)) + ')')
        code = '\n'.join(chunks)
        exec code
        return f(*seqs)

    a = "abcde"*10
    b = range(99)
    c = [x**2 for x in range(33)]
    seqs = [a, b, c]

    if __name__ == "__main__":
        assert list(count_combinations(seqs)) == list(cg_combinations(seqs))

        import timeit
        test = timeit.Timer('list(count_combinations(seqs))',
               'from __main__ import count_combinations, seqs')
        t1 = test.timeit(number=10)
        test = timeit.Timer('list(cg_combinations(seqs))',
               'from __main__ import cg_combinations, seqs')
        t2 = test.timeit(number=10)
        print t1, t2
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://projects.scipy.org/pipermail/numpy-discussion/attachments/20071226/b7ef6f25/attachment.html 


More information about the Numpy-discussion mailing list