Combinations (was Re: Permutations algoritm?)

[Anton Vredegoor]

On Fri, 15 Nov 2002 15:51:04 -0600, sismex01 at hebmex.com wrote:

>Of a set of different items 'S', obtain all distinct subsets of 'n'
>items where all items in the subset are different.
>
>So, if I have, for example:
>
>   S = [ 0, 1, 2, 3 ]
>
>the universe of available subsets of 3 items would be:
>
>   s = [ (0, 1, 2),
>         (0, 1, 3),
>         (0, 2, 3),
>         (1, 2, 3) ]
>
>the universe of available subsets of 2 items would be:
>
>   s = [ (0, 1),
>         (0, 2),
>         (0, 3),
>         (1, 2),
>         (1, 3),
>         (2, 3) ]

In order to make the title conform to what is described above, I had
to start a new thread, I hope you will find it!

Below is my current state of the art combinations algo, I would
welcome improvements. It's a bit long perhaps, but its supports
indexed combinations and can index large sets.

Regards,
		Anton.

class combinations:
    
    def __init__(self,n,k):
        self.n,self.k = n,k
        self.count = self.noverk(n,k)
    
    def __getitem__(self,index):
        #combination number index
        if index > self.count - 1:
             raise IndexError
        result = []
        pos,n,k = 0,self.n,self.k
        treshold = self.treshold
        for i in range(k):
            offset, index = treshold(index,n-i-pos,k-i)
            pos += offset 
            result.append(pos+i)
        return result
        
    def noverk(self,n,k):
        #compute n over k
        result = 1l
        for i in range(k):
            result = result*(n-i)/(i+1)
        return result
    
    def treshold(self,val,n,k):
        #cumulative treshold on a diagonal of pascals triangle 
        cum,tresh,rest = 0,0,0
        noverk = self.noverk
        for i in range(n-k+1):
            x = noverk(n-i-1,k-1)
            cum += x
            if cum > val:
                rest = val + x - cum
                break
            tresh += 1
        return tresh, rest

def test():
    comb = combinations(4,2)
    print comb.count
    for c in comb:
        print c
    
if __name__ == '__main__':
    test()