Partitioning {1,..,n}
By Rob Kinley on Monday, November 27, 2000
- 02:18 am:
Hello,
I am looking for a code/algorithm
that would generate all possible subset partitions of S =
{1,..,n}.
For example, if S = {1,2,3} then there are partitions such
as:
A = {1}, B ={2,3};
A = {1,2}, B = {3};
A = {1,3}, B = {2};
etcetera
Also, I wish to regard A= {2,1} as distinct from A={1,2}, so
after identifying these subsets, I need to permute them.
I would greatly appreciate it if you could provide me with some
guidance on this.
By Dan Goodman (Dfmg2) on Monday,
November 27, 2000 - 05:00 pm:
If you're programming in C or C++, then there's a function
called next_permutation(...) which you'll find useful. If n £ 32, then
there's a nice way of finding all subsets of {1,¼,n}. Every subset of
{1,¼,n} can be paired off with a number between 0 and 2n-1 in the
following way. You define the ïndicator function" IX of a subset X of
{1,¼,n} as follows: IX(x)=0 if x is not in X or 1 if x is in
X. Let
. You can easily see that every
subset has a unique number using this function, and that every number between
0 and 2n-1 gives rise to a unique subset. On a computer it's easy to test
whether or not a given element is in the subset generated by a number k, you
just extract the ith bit to test if i is in the subset, in C++ you write
if(k&(1< < i)) to make this test. You can use this to generate all the
subsets of a set in the following way. In C++ the program would look like this
(for subsets of {0,¼,n-1}):
unsigned int max_n = 0;
for(int i=0;i< n;i++) max_n|=1< < i;
for(unsigned int k=0;k< =max_n;k++)
{
for(int i=0;i< n;i++)
{
if(k&(1< < i))
{
// then i is in the kth subset
}
}
}
Once you've gotan array with a subset, say an array int *subset of
size int m, then you can use the following C++ code to go through all
the permutations of it
// do stuff to the first permutation here
while(next_permutation(subset,m))
{
// do stuff to the current permutation here
}
Hopefully that will have gotten the ideas across even if you don't know C++,
but post again if that's not entirely clear.
Finally, note that if your C++ compiler has the (non-standard) long
long datatype, then you can use the code above for subsets of anything up
to n=64 by changing the unsigned int to an unsigned long
long.