Search   Memberlist   Usergroups
 Page 1 of 1 [4 Posts]
Author Message
--CELKO--
science forum beginner

Joined: 04 May 2005
Posts: 23

Posted: Fri Jun 30, 2006 5:24 pm    Post subject: Set Partitioning algorithm

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?
Christopher J. Henrich
science forum Guru Wannabe

Joined: 03 May 2005
Posts: 107

Posted: Fri Jun 30, 2006 6:05 pm    Post subject: Re: Set Partitioning algorithm

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
mensanator@aol.compost
science forum Guru

Joined: 24 Mar 2005
Posts: 826

Posted: Fri Jun 30, 2006 8:51 pm    Post subject: Re: Set Partitioning algorithm

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

"""
jasen
science forum beginner

Joined: 28 Jun 2006
Posts: 16

Posted: Sat Jul 01, 2006 8:18 am    Post subject: Re: Set Partitioning algorithm

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
Google

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [4 Posts]
 The time now is Wed Mar 20, 2019 7:11 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am Name of algorithm for pairwise comparison ? Paul Nutteing Math 10 Fri Jul 14, 2006 6:55 am Need an algorithm Dave111 Math 4 Fri Jul 14, 2006 2:19 am A POSSIBLE FACTORING ALGORITHM Achilleas D Palamiotis Math 7 Thu Jul 13, 2006 6:14 am 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.0109s ][ Queries: 16 (0.0008s) ][ GZIP on - Debug on ]