A puzzle for Pythonistas

[Anton Vredegoor]

On 31 Jan 2003 04:59:17 -0800, alan_salmoni at yahoo.com (Alan James
Salmoni) wrote:

>The problem is defined like this: I have a list of unique integers,
>and the list is of arbitrary length, though 2 elements is the minimum.
>Using each integer only once, what are the possible combinations of 2
>or more elements that can be derived from this list. I know how to

Since the list is of arbitrary length the number of combinations can
become extremely large. If that is the case, indexed combinations are
preferable instead of generating or computing the whole list of
combinations, because of time or memory limitations. For an example
see some code below. It's not tested thoroughly.

Regards,
		Anton.


class combinations:
    
    def __init__(self,n,k):
        self.n,self.k,self.count = n,k, self.noverk(n,k)
    
    def __getitem__(self,index):
        #combination number index
        if index > self.count - 1: raise IndexError
        res,pos,n,k,rest = [],0,self.n,self.k,index
        for i in range(k):
            offset, rest = self.treshold(rest,n-i-pos,k-i)
            pos += offset 
            res.append(pos+i)
        return res
        
    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,val
        for i in range(n-k+1):
            x = self.noverk(n-i-1,k-1)
            if rest - x < 0:
                return i,rest
            rest -= x
    
class allcombinations:
    
    def __init__(self,n):
        self.n = n
        self.count = 2**n
    
    def __getitem__(self,index):
        #combination number index for all k in combinations(n,k)
        if index > self.count - 1: raise IndexError        
        n,rest = self.n,index
        for k in range(n+1):
            c = combinations(n,k)
            if rest - c.count < 0:
                return c[rest]
            rest -= c.count

def test():
    L = list("abcd")
    n = len(L)
    a = allcombinations(n)
    start = combinations(n,0).count+combinations(n,1).count
    finish = a.count
    for i in range(start,finish):
        print [L[x] for x in a[i]]
    
if __name__ == '__main__':
    test()