Algorithm: combinations of (k) taken from (n) values

Darrell darrell at dorb.com
Sun Apr 9 07:16:13 CEST 2000


Pasted the Charles algorithm into a class using a coroutine to provide
iterators.
The idea being to make the algorithm lazy.
Is it possible to figure out a combination at some huge offset without
figuring out all previous combinations? Seems like it might be, in which
case the isn't much use.

import coroutine
class Choices:
    def __init__(self,n,k=None) :
        """
        Prepares to return elements from a list consisting of all k-element
(ordered)
        subsets of {0 ... n-1}.
        """
        self._combinations=[]
        self._skip=1

        def combs(n=n,k=k, self=self):
            """returns sorted list of k items taken from n."""
            l=self._combinations
            if k==None:
                k=n
            for c in range(n):
                l.append([c])
            for i in range(k-1):
                li = []
                for c in l:
                    for j in range(c[-1]+1,n):
                        li.append(c+[j])
                            // Bet Christian can show me a better way to do
this.
                        if self._skip==0:
                            self._combinations=li
                            coroutine.resume_caller (li[-1])
                        self._skip=self._skip-1

                l = li
            return l

        self._coroutine=coroutine.coroutine(combs)

    def next(self):
        self._skip=1
        return self._coroutine.resume()

    def __getitem__(self, i):
        if i < len(self._combinations):
            return self._combinations[i]
        cnt=i-len(self._combinations)+1
        self._skip=cnt
        self._coroutine.resume()
        return self._combinations[i]

    def __getslice__(self, i, j):
        self[j]
        return self._combinations[i:j]

choices=Choices(30,2)
for x in range(3):
    print choices.next()

print 'getitem:',choices[7]
print 'getslice:', choices[40:50]







More information about the Python-list mailing list