FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Recreational
Set Partitioning algorithm
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
--CELKO--
science forum beginner


Joined: 04 May 2005
Posts: 23

PostPosted: Fri Jun 30, 2006 5:24 pm    Post subject: Set Partitioning algorithm Reply with quote

Given a finite set of (n) elements {1, 2, 3,..} :

1) How many distinct contigous partitions can you make? That is,
P(1) = {{1, 2, 3}}, 1 way
P(2) = {{1}, {2, 3}} , {{1, 2} ,{3}} , (n-1) ways
P(3) = {{1}, {2}, {3}} 1 way

Obviously there is only way to make one partition and only one way to
make (n) partitions.

2) Is there a good algorithm for generating these partitions?
Back to top
Christopher J. Henrich
science forum Guru Wannabe


Joined: 03 May 2005
Posts: 107

PostPosted: Fri Jun 30, 2006 6:05 pm    Post subject: Re: Set Partitioning algorithm Reply with quote

In article <1151688257.840370.246680@i40g2000cwc.googlegroups.com>,
--CELKO-- <jcelko212@earthlink.net> wrote:

Quote:
Given a finite set of (n) elements {1, 2, 3,..} :

1) How many distinct contigous partitions can you make? That is,
P(1) = {{1, 2, 3}}, 1 way
P(2) = {{1}, {2, 3}} , {{1, 2} ,{3}} , (n-1) ways
P(3) = {{1}, {2}, {3}} 1 way

Obviously there is only way to make one partition and only one way to
make (n) partitions.

2) Is there a good algorithm for generating these partitions?

Donald E. Knuth, _The Art of computer Programming_, Volume 4, Fascicle

3, "Generating All Combinations and Partitions," ISBN 0-201-85394-9,
will tell you all you want to know. And then some. Don't forget to do
ALL the exercises.

--
Chris Henrich
http://www.mathinteract.com
"It's our supreme ability and willingness to screw up that is the secret of our
success."
-- R. X. Cringely
Back to top
mensanator@aol.compost
science forum Guru


Joined: 24 Mar 2005
Posts: 826

PostPosted: Fri Jun 30, 2006 8:51 pm    Post subject: Re: Set Partitioning algorithm Reply with quote

--CELKO-- wrote:
Quote:
Given a finite set of (n) elements {1, 2, 3,..} :

1) How many distinct contigous partitions can you make? That is,
P(1) = {{1, 2, 3}}, 1 way
P(2) = {{1}, {2, 3}} , {{1, 2} ,{3}} , (n-1) ways
P(3) = {{1}, {2}, {3}} 1 way

This looks the same as asking how many ways can D items
be put in W containers such that each container has 1 item.

For D=3 W=2, I get

1,2
2,1

which can be interpreted as the number of items inside the braces {}.
so 1,2 is

{{1}, {2,3}}
^ ^
| |
| 2 items
1 item

If that's right, then P(W) is C(D-1,W-1), the combination formula,
which is

(D-1)!
------------------
(W-1)!(D-1 - W-1)!

The total partitions are then the sum of each P(W). for D=4,

P(1) = 1
P(2) = 3
P(3) = 3
P(4) = 1

And the sum of all partitions is 2**(D-1)

Quote:

Obviously there is only way to make one partition and only one way to
make (n) partitions.

2) Is there a good algorithm for generating these partitions?

Assuming this is actually what you want:

For N=4

P(1):
4 {{1,2,3,4}}

P(2):
1,3 {{1},{2,3,4}}
2,2 {{1,2},{3,4}}
3,1 {{1,2,3},{4}}

P(3):
1,1,2 {{1},{2},{3,4}}
1,2,1 {{1},{2,3},{4}}
2,1,1 {{1,2},{3},{4}}

P(4):
1,1,1,1 {{1},{2},{3},{4}}


Then the answer is yes (Python).


import sys
import gmpy

def move_col(c):
sv[c-1] += 1
sv[c] -= 1

def find_c():
i = -1
while i<0:
if sv[i]>1:
return i
i -= 1

def rollover(c):
move_col(c)
sv[-1] = sv[c]
sv[c] = long('1')

def print_sv():
svs = ""
for s in sv:
svs = svs + str(s) + ","
print svs[:-1]

depth = long(sys.argv[1])
width = long(sys.argv[2])

if depth<width:
print 'depth',depth,'must be greater than width',width
sys.exit()

max_element = depth - width + 1

sv = []

for i in range(width):
sv.append(long('1'))

sv[-1] = max_element

print_sv()
pcount = 1

while sv[0]<max_element:
c = find_c()
if c < -1:
rollover(c)
print_sv()
pcount += 1
else:
move_col(c)
print_sv()
pcount += 1

print
print ' actual partitions:',pcount
print 'C(depth-1,width-1):',gmpy.comb(depth-1,width-1)

"""

L:\user_home\partitions>partition_counter 8 4
1,1,1,5
1,1,2,4
1,1,3,3
1,1,4,2
1,1,5,1
1,2,1,4
1,2,2,3
1,2,3,2
1,2,4,1
1,3,1,3
1,3,2,2
1,3,3,1
1,4,1,2
1,4,2,1
1,5,1,1
2,1,1,4
2,1,2,3
2,1,3,2
2,1,4,1
2,2,1,3
2,2,2,2
2,2,3,1
2,3,1,2
2,3,2,1
2,4,1,1
3,1,1,3
3,1,2,2
3,1,3,1
3,2,1,2
3,2,2,1
3,3,1,1
4,1,1,2
4,1,2,1
4,2,1,1
5,1,1,1

actual partitions: 35
C(depth-1,width-1): 35

"""
Back to top
jasen
science forum beginner


Joined: 28 Jun 2006
Posts: 16

PostPosted: Sat Jul 01, 2006 8:18 am    Post subject: Re: Set Partitioning algorithm Reply with quote

On 2006-06-30, --CELKO-- <jcelko212@earthlink.net> wrote:
Quote:
Given a finite set of (n) elements {1, 2, 3,..} :

1) How many distinct contigous partitions can you make? That is,

2^(n-1)

Quote:
P(1) = {{1, 2, 3}}, 1 way
P(2) = {{1}, {2, 3}} , {{1, 2} ,{3}} , (n-1) ways
P(3) = {{1}, {2}, {3}} 1 way

Obviously there is only way to make one partition and only one way to
make (n) partitions.

2) Is there a good algorithm for generating these partitions?

look at the gaps between the elements.

00 {{1, 2, 3}}
01 {{1, 2} ,{3}}
10 {{1}, {2, 3}}
11 {{1}, {2}, {3}}

Bye.
Jasen
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Fri Jun 23, 2017 12:07 am | All times are GMT
Forum index » Science and Technology » Math » Recreational
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am
No new posts Name of algorithm for pairwise comparison ? Paul Nutteing Math 10 Fri Jul 14, 2006 6:55 am
No new posts Need an algorithm Dave111 Math 4 Fri Jul 14, 2006 2:19 am
No new posts A POSSIBLE FACTORING ALGORITHM Achilleas D Palamiotis Math 7 Thu Jul 13, 2006 6:14 am
No new posts Algorithm to fit rectangles with different areas inside a... Dani Camps Research 0 Tue Jul 11, 2006 9:14 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0207s ][ Queries: 16 (0.0035s) ][ GZIP on - Debug on ]