# Python and Combinatorics

Discussion in 'Python' started by Nic, May 16, 2006.

1. ### NicGuest

Hello,
I've a problem in defining a good Python code useful to articulate the
following algorithm.
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.

Nic, May 16, 2006

2. ### Peter OttenGuest

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

Peter Otten, May 16, 2006

3. ### NicGuest

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

"Peter Otten" <> ha scritto nel messaggio
news:e4c0dh\$197\$03\$-online.com...
> 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
>

Nic, May 16, 2006
4. ### Peter OttenGuest

Nic wrote:

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

Peter Otten, May 16, 2006
5. ### Gerard FlanaganGuest

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

Gerard Flanagan, May 16, 2006