Velocity Reviews > Python and Combinatorics

Python and Combinatorics

Nic
Guest
Posts: n/a

 05-16-2006
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
Guest
Posts: n/a

 05-16-2006
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
Guest
Posts: n/a

 05-16-2006
I forgot them. Sorry.
They should be included.
Nic

"Peter Otten" <(E-Mail Removed)> ha scritto nel messaggio
news:e4c0dh\$197\$03\$(E-Mail Removed)-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
>
> PS: Please don't top-post.

Peter Otten
Guest
Posts: n/a

 05-16-2006
Nic wrote:

>> PS: Please don't top-post.

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
Guest
Posts: n/a

 05-16-2006
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