473,289 Members | 1,923 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,289 software developers and data experts.

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.
May 16 '06 #1
4 2855
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.
May 16 '06 #2
Nic
I forgot them. Sorry.
They should be included.
Nic

"Peter Otten" <__*******@web.de> ha scritto nel messaggio
news:e4*************@news.t-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.

May 16 '06 #3
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
May 16 '06 #4
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

May 16 '06 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: Xah Lee | last post by:
a year ago i wrote this perl program as part of a larger program. as a exercise of fun, let's do a python version. I'll post my version later today. =pod combo(n) returns a collection with...
17
by: Carnosaur | last post by:
Hi all, I am trying to write a program that will enumerate all possible combinations of assigning 1 to 4 colors to 4 objects. For example, there is one way to assign a single color to four...
0
by: Cameron Laird | last post by:
QOTW: "Dangit! I need to find a less honest programming language. Anyone have a Perl cookbook handy? ..." - Lonnie Princehouse "The pursuit of orthogonality, while admirable, can lead to...
2
by: Cameron Laird | last post by:
QOTW: "Making a user class work anywhere you can put a mapping in Perl is deep magic, but easy in Python. Creating types that act like files and can be used wherever a file is used is SOP in...
0
by: Gabriel Genellina | last post by:
QOTW: "So I never let the age of the universe intimidate me." - mensanator, on (roughly) the occurrence of large integral exponents in combinatorics and more "You're coming from a Perl...
19
by: Terry Reedy | last post by:
"Luis Zarrabeitia" <kyrie@uh.cuwrote in message news:200805081914.06459.kyrie@uh.cu... | Btw, there seems to be a math problem in python with exponentiation... | >>0**0 | 1 | That 0^0 should be...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.