Shell Programming and Scripting

from time import time

def combinations(list, k):
    """Choose combinations of list, choosing k elements(no repeats)"""
    A=[]
    if len(list) < k:
        return []
    else:
        seq = [i for i in range(k)]
        while seq:
            #print[list[index] for index in seq]
            if[list[index] for index in seq] not in A:
                A.append([list[index] for index in seq])
            seq = get_next_combination(len(list), k, seq)
        return A

def get_next_combination(num_elements, k, seq):
        index_to_move = find_index_to_move(num_elements, seq)
        if index_to_move == None:
            return None
        else:
            seq[index_to_move] += 1
            #for every element past this sequence, move it down
            for i, elem in enumerate(seq[(index_to_move+1):]):
                seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1
            return seq

def find_index_to_move(num_elements, seq):
        """Tells which index should be moved"""
        for rev_index, elem in enumerate(reversed(seq)):
            if elem < (num_elements - rev_index - 1):
                return len(seq) - rev_index - 1
        return None

def main(n,p):

    F=combinations(range(1,n+1),p)
    print len(F)

if __name__ == '__main__':

    start=time()
    main(50,3)
    end=time()
    print "total time:",end-start

kent$ time python pySolution.py
2118760
python pySolution.py  167.13s user 0.64s system 98% cpu 2:50.08 total

$ time ./em.py > out

real    0m10.227s
user    0m9.926s
sys     0m0.300s

$ wc -l out
 2118760 out

#!/usr/bin/env python

def perms(n, p):
    a = []
    j = p
    for i in range(p):
        a.append(j)
        j -= 1

    while True:
        print a
        for i in range(p):
            if a[i] < n - i:
                a[i] += 1
                for j in range(0, i):
                    a[j] = a[i] + i - j
                    break
        else:
            break

if __name__ == '__main__':
    perms(50, 5)

kent$ time -p ./t.py > a.tmp
real 6.98
user 6.81
sys 0.15
kent$ wc -l a.tmp
2118760 a.tmp

kent$ cat /proc/cpuinfo| ack "model name"    
model name	: Intel(R) Core(TM)2 CPU         T5600  @ 1.83GHz
model name	: Intel(R) Core(TM)2 CPU         T5600  @ 1.83GHz