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

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post David Palm Ruby 7 02-18-2010 04:08 PM none Python 4 10-26-2007 07:41 AM Xah Lee Perl Misc 5 02-11-2005 10:05 AM Xah Lee Python 7 02-11-2005 10:05 AM Carnosaur C Programming 17 10-31-2003 03:48 PM

Advertisments