Python and Combinatorics

[Gerard Flanagan]

Nic wrote:
> Hello,
> I've a problem in defining a good Python code useful to articulate the
> following algorithm.
> Can you help  me please?
> Thanks a bunch,
> Nic
>
> 1. Insert a number "n".
> Example: 3
>
> 2. List all the numbers < or = to n.
> Example: 1,2,3.
>
> 3. Combine the listed numbers each other.
> Example:
> 12
> 13
> 23
>
> 4. For each combination associate two letters a and b.
> Example:
> 12a
> 12b
> 13a
> 13b
> 23a
> 23b
>
> 5. Combine the new combinations each other, provided that combinations
> including the same couple of numbers (e.g. 12a and 12b) cannot be combined.
> Example:
> 12a 13a 23a
> 12a 13b 23a
> 12a 13b 23b
> 12b 13a 23a
> 12b 13b 23a
> 12b 13b 23b
>
> PS
> 12a 13a 23a and13a 23a 12a are the same thing.

This might get you some of the way:

def nkRange(n,k):
    m = n - k + 1
    indexer = range(0, k)
    vector = range(1, k+1)
    last = range(m, n+1)
    yield vector
    while vector != last:
        high_value = -1
        high_index = -1
        for i in indexer:
            val = vector[i]
            if val > high_value and val < m + i:
                high_value = val
                high_index = i
        for j in range(k - high_index):
            vector[j+high_index] = high_value + j + 1
        yield vector


X = [ ''.join(map(str,x)) + y for x in nkRange(3,2) for y in ['a','b']
]
print X

def kSubsets( alist, k ):
    n = len(alist)
    for vector in nkRange(n, k):
        ret = []
        for i in vector:
            ret.append( alist[i-1] )
        yield ret

Y = [ ''.join(x) + y for x in kSubsets( '123', 2 ) for y in ['a','b']]
print Y

['12a', '12b', '13a', '13b', '23a', '23b']

(a 'cross product' function may also help you - search this Group)

Gerard