Date: 22 Apr 1998 13:46:54 GMT
From: meleis@coe.neu.edu (Waleed Meleis)
Subject: Random partitions
Hello, I'm looking for an efficient way to compute a random partition of a
fixed integer n such that every distinct partition is equally likely.
By "partition of an integer", I mean a set of integers that sums to n. The partitions of 4 are: {4},{3,1},{2,2},{2,1,1},{1,1,1,1}.
Any information would be appreciated. An email reply would be great. Thanks.
Waleed Meleis
meleis@ece.neu.edu
Date: 22 Apr 1998 20:59:42 GMT
From: israel@math.ubc.ca (Robert Israel)
Subject: Random partitions
Start by precomputing the number p_k(m) of partitions of m with each term <= k,
for m = 1 .. n and k = 1 .. m. This can be obtained by the recursion
p_k(m) = sum_{j = 0}^floor(m/k) p_{k-1}(m-jk) for k <= m
(noting that p_k(m) = p_m(m) for k > m). In the process, store the partial sums s(k,m,l) = sum_{j = 0}^l p_{k-1}(m-jk) for k <= m, l <= m/k. This computation takes O(n^2 ln(n)) arithmetic operations.
Now the following pseudocode procedure produces a random partition of m with each term <= k, where m <= n. So to get a random partition of n you would use randpart(n,n).
function randpart(m,k: integer): partition;
if k > m then return randpart(m,m)
else if k = 1 then return m 1's
else
choose j in 0, 1, ..., floor(m/k) with probabilities
P(j) = p_{k-1}(m-jk)/p_k(m);
return j k's + randpart(m-jk, k-1)
end
Note that the step of choosing j can be done as follows: generate a random
number X in [0,1] and use binary search to find the least j so that
s(k,m,j) >= X p_k(m).
Robert Israel israel@math.ubc.ca Department of Mathematics (604) 822-3629 University of British Columbia fax 822-6074 Vancouver, BC, Canada V6T 1Z2Date: 23 Apr 1998 19:17:09 GMT
{4,0,0}, {0,4,0}, {0,0,4}, {3,1,0}, {3,0,1}, {1,3,0},
{0,3,1}, {1,0,3}, {0,1,3}, {2,1,1}, {1,2,1}, {1,1,2},
{2,2,0}, {2,0,2}, {0,2,2}
For a specific number of partitions, it can be done as follows:Using a deck of playing cards, set aside n red cards, and p-1 black cards (p being the number of partitions). Take the cards set aside and shuffle thoroughly. Then lay them out face-up from left to right. Count the number of reds between blacks or between blacks and the outer limits and you have your partitions. Any appropriate size group of physical items marked in an appropriate way can be used by simply doing a random selection without repetitions.
If by efficient you mean that you'll be working with very large sets and/or generating large numbers of combinations, making physical representations of partitions impractical, then a computer program can be used. The key is ensuring the method used to determine the combination chosen meets your standard of "random". It may be necessary to incorporate at least one physical action to make every choice "equally likely".
If this is not what you meant in your post, you'll have to rephrase your question, be more specific as to what you're looking for, and provide a better example of what you want.
Derek Asari
eq069@cleveland.freenet.edu
Date: Mon, 13 Apr 1998 12:34:34 -0500
From: Christos Makrigeorgis <christos_makrigeorgis@sabre.com>
Subject: Enumeration on multisets
Hello OR/CS world:
Given a multiset M = {A,B,C} where A={a1,a2,a3}, B={b1,b2} and C={c1,c2,c3}.
I was looking for any hints or refs to an efficient algorithm to generate the 3x2x3 possible sets each containing a unique element from A, a unique element from B and a unique element from C (i.e., an algorithm to generate {a1,b1,c1}, {a1,b1,c2}, ..., {a3,b2,c3}). Obviously 3 loops will do the trick (the cardinality of sets A, B, C is known a priori) but I would like to look at a better enumeration algorithm independedent of loop constructs (or if not possible, one containing at most 2 loops?).
-- Thanks.
--------------------------------------- Christos Makrigeorgis STS, The SABRE Group, AMR Corp Christos_Makrigeorgis@sabre.com ---------------------------------------Date: Mon, 13 Apr 1998 13:33:47 -0500
Hello,
Here's some C code to do this (indices are 0-based, not 1-based as in your example)
ia = ib = ic = 0;
while (1)
{
<<< here we choose element ia from A, ib from B, ic from C >>>>
/* increment to next element in enumeration */
if (++ia == na)
ia = 0;
if (++ib == nb)
{
ib = 0;
if (++ic == nc)
break; // all done
}
}
} /* end while() */
One could replace the complicated if block by a loop over set indices placed
in an array -- this would accomodate an arbitrary number of sets while still
using only 2 loops
Wesley T. Perkins
wesley@starbath.com
Date: 14 Apr 1998 22:17:13 GMT
From: eq069@cleveland.Freenet.Edu (Derek T. Asari)
Subject: Enumeration on multisets
To enumerate the permutations, assign values ranging from 0 to
sizeofset-1 to each member of the base sets, and treat each
permutation as a mixed-radix number. For example, {a1,b2,c3}
would be the mixed-radix number 012. This number can then be
converted to a unique decimal number (in this case, 0*(2*3) + 1*3
+ 2*1 = 5) in the range of 0 to (SizeOfA * SizeOfB * SizeOfC) -1
or in this case 17.
Generating permutations could be accomplished by reversing the process and taking a number between 0 and (in this case) 17, and performing a series of modulus and integer division operations.
Derek Asari
eq069@cleveland.freenet.edu
Date: Tue, 14 Apr 1998 18:44:07 -0700
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: Enumeration on multisets
> Derek T. Asari wrote:
To enumerate the permutations, assign values ranging from 0 to sizeofset-1 to each member of the base sets, and treat each permutation as a mixed-radix number. For example, {a1,b2,c3} would be the mixed-radix number 012. This number can then be converted to a unique decimal number (in this case, 0*(2*3) + 1*3 + 2*1 = 5) in the range of 0 to (SizeOfA * SizeOfB * SizeOfC) -1 or in this case 17.
Generating permutations could be accomplished by reversing the process and taking a number between 0 and (in this case) 17, and performing a series of modulus and integer division operations.
-----------
The writer asks for an enumeration, in which case I see no advantage of going 0..17 instead of 1..3 x 1..2 x 1..3.
In response to the original question, I'd say that you can in essence never have two loops when there are three sets to be enumerated.
Am I overlooking something obvious here?
Roy Jonker @ MagicLogic Optimization Inc.
Crawl back to front page.