Python and Combinatorics

[Nic]

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.

 

[Peter Otten]

Nic wrote:

[Algorithm that I may have misunderstood]

12a 13a 23a
12a 13b 23a
12a 13b 23b
12b 13a 23a
12b 13b 23a
12b 13b 23b

What about 12a 13a 23b and 12b 13a 23b?

Peter

PS: Please don't top-post.

 

[Nic]

I forgot them. Sorry.
They should be included.
Nic

Nic wrote:

[Algorithm that I may have misunderstood]

12a 13a 23a
12a 13b 23a
12a 13b 23b
12b 13a 23a
12b 13b 23a
12b 13b 23b

What about 12a 13a 23b and 12b 13a 23b?

Peter

PS: Please don't top-post.

 

[Peter Otten]

You probably overlooked that

Here's a naive implementation:

from itertools import izip

def unique(items, N):
assert N > 0
if N == 1:
for item in items:
yield item,
else:
for index, item in enumerate(items):
for rest in unique(items[index+1:], N-1):
yield (item,) + rest

def repeat(*items):
assert len(items)
if len(items) == 1:
for item in items[0]:
yield item,
else:
for item in items[0]:
for rest in repeat(*items[1:]):
yield (item,) + rest

def render():
pairs = list(unique(range(1, 4), 2))
for item in unique(pairs, 3):
for suffix in repeat(*["ab"]*3):
yield tuple((a, b, s) for (a, b), s in izip(item, suffix))

if __name__ == "__main__":
for item in render():
print " ".join("%s%s%s" % t for t in item)

Peter

 

[Gerard Flanagan]

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
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