Combinatorial: Build 10 groups of 100 elements while the elements remain sorted
I have a problem with combinatorics. Unfortunately, I cannot describe it in the abstract, so I am trying to explain it as a story. :)
Problem:
- There are 100 children in the schoolyard.
- All of them have a unique height if the values are 100-199 cm.
- You want to create 10 groups, each with 1-99 children.
- How can you create all groups as long as children have to be sorted by height?
- I need all the possible solutions for these groups, since it is not difficult to find one constellation.
In short and easy:
All 100 children stand side by side. You only need to decide where to divide them into groups and find all the solutions for that.
Example (values are heights):
[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] impossible
[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] possibly
I hope you can help me. Thank you so much in advance!
PS: This is not homework.;) I usually need a function that does this with numbers. But I could not describe it in the abstract, as "building k groups of numbers, and all numbers are sorted." I thought you wouldn't understand it that way. :) A PHP solution would be better, but I would be glad to see solutions in other languages. :)
source to share
As I understand it, you are really asking for ways of dividing the interval [100, 199] into 10 parts, i.e. you want to find numbers x [0], ..., x [10] such that:
x[0] = 100 < x[1] < x[2] < ... < x[9] < x[10] = 199
Define a recursive function partition(intervalSize, pieces)
that counts the number of ways to split a given interval. You are after partition(100, 10)
.
The following Java code counts sections (sorry, I don't know PHP so well):
public class Partitions
{
static long[][] partitions = new long[100][10];
private static long partition(int intervalSize, int pieces)
{
if (partitions[intervalSize-1][pieces-1] != 0) {
return partitions[intervalSize-1][pieces-1];
}
long partition = 0L;
if (pieces == 1) {
partition = 1L;
} else {
for (int i = 1; i <= intervalSize - 1; i++) {
partition += partition(intervalSize - i, pieces - 1);
}
}
partitions[intervalSize-1][pieces-1] = partition;
return partition;
}
public static void main(String[] args)
{
System.out.println(partition(100, 10));
}
}
The following Java code prints the actual sections. Since the number of partitions is so large for (100,10), I illustrate the answer for (5,3):
public class Partitions2
{
private static void showPartitions(int sizeSet, int numPartitions)
{
showPartitions("", 0, sizeSet, numPartitions);
}
private static void showPartitions(String prefix, int start, int finish,
int numLeft)
{
if (numLeft == 0 && start == finish) {
System.out.println(prefix);
} else {
prefix += "|";
for (int i = start + 1; i <= finish; i++) {
prefix += i + ",";
showPartitions(prefix, i, finish, numLeft - 1);
}
}
}
public static void main(String[] args)
{
showPartitions(5, 3);
}
}
Output:
| 1, | 2, | 3,4,5, | 1, | 2.3, | 4.5, | 1, | 2,3,4, | 5, | 1,2, | 3, | 4,5, | 1,2, | 3,4, | 5, | 1,2,3, | 4, | 5,
source to share
I need all possible solutions for these groups, since it is not difficult to find one constellation.
Usually there are 100! ways to permute by 100 positions, but since you are saving the order, you can significantly reduce the size of the problem. What you are describing is a whole separation problem . For example, suppose you split the number 5 into all possible integer subsets up to 5, you get the sets {5}, {4, 1}, {3, 2}, {3, 1, 1,}, {2 , 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.
The number of whole partitions grows exponentially with the size of an integer, but the exponential growth is slow enough for you to list all the partitions n = 100, since there are only 190,569,292 of them. An additional limitation here is that you want to filter all of your sections for sets containing exactly 10 elements, which is easy to list using a Ferrer chart.
I can demonstrate a Ferrer diagram by dividing the number 20 by 3 buckets: start with a 20 col x 3 row grid like this:
12345678901234567890 1****************** 2 * 3 *
So the first section is {18, 1, 1}
Now move the item from the top of the stack to the next slot:
12345678901234567890 1***************** 2 ** 3 *
Our new section is {17, 2, 1}. We can use another item from one stack to another:
12345678901234567890 1**************** 2 *** 3 *
We now have {16, 3, 1}. You continue this way until you have listed all the permutations (up to you, regardless of whether {17, 1, 2} is a separate section from {17, 2, 1}).
From this point of view, you should be able to provide a general outline of the algorithm that you need, that is, if you want to write this function from scratch. Other people are already writing many powerful functions to solve the problem easily.
source to share