組み合わせ論:要素を並べ替えたまま、100 個の要素からなるグループを 10 個構築する
-
20-09-2019 - |
質問
組み合わせ論に関する問題があります。残念ながら抽象的には説明できないので、物語として説明してみます。:)
問題:
- 校庭には100人の子供たちがいます。
- 値が 100 ~ 199cm であると仮定すると、それらはすべて固有の高さを持ちます。
- それぞれが 1 ~ 99 人の子で構成される 10 個のグループを作成するとします。
- 子供を身長順に並べ替える必要があるときに、どのようにしてすべてのグループを作成できるでしょうか?
- 1 つの星座を見つけるのは難しくないため、これらのグループに対して考えられるすべての解決策が必要です。
短くて簡単:
100人の子どもたち全員が並んで立っています。必要なのは、どこでグループに分割するかを決定し、これに対するすべての解決策を見つけることだけです。
例 (値は高さです):
[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] 不可能である
[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] 可能だ
助けていただければ幸いです。事前にどうもありがとうございました!
追伸:宿題じゃないよ。;) 通常、これを数値で行う関数が必要です。しかし、これを「すべての数値がソートされている間に k 個の数値グループを構築する」というように抽象的に説明することはできませんでした。このままでは理解できないと思いました。:) PHP でのソリューションが最適ですが、他の言語でのソリューションも見てみたいと思います。:)
解決
私の理解では、あなたは効果的に10個の部分に間隔[100199]を分割する方法を求めている、あなたは数字xを見つけたい、すなわち、[0]、...、X [10]、このようなこと:
x[0] = 100 < x[1] < x[2] < ... < x[9] < x[10] = 199
一定の間隔を分割する方法の数をカウント再帰関数のpartition(intervalSize, pieces)
を定義します。あなたはpartition(100, 10)
後です。
次のJavaコードは(申し訳ありませんが、うまくPHPを知らない)パーティションをカウントします:
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));
}
}
次のJavaコードは、実際のパーティションを出力します。パーティションの数は、(100,10)のための非常に高いですので、私は(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);
}
}
出力されます:
|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,
他のヒント
これらのグループには、1つの星座を見つけるのは難しくないため、すべての可能なソリューションが必要です。
通常は100個あります!100 個の項目を並べ替える方法もありますが、順序は維持されるため、問題のサイズを小さくすることができます。 実質的に. 。あなたが説明しているのは、 整数分割問題. 。たとえば、数値 5 を、合計で 5 になるすべての可能な整数のサブセットに分割すると、セット {5}、{4, 1}、{3, 2}、{3, 1, 1 が得られます。 、}、{2、2、1}、{2、1、1、1}、{1、1、1、1、1}。
整数パーティションの数は、整数のサイズに応じて指数関数的に増加しますが、指数関数的な増加は十分に遅いため、n = 100 のすべてのパーティションを列挙できます。これは、パーティションが 190,569,292 個しかないためです。ここでの追加の制約は、ちょうど 10 個の項目を含むセットのすべてのパーティションをフィルターすることです。これは、フェレール図を使用すると簡単に列挙できます。
数値 20 を 3 つのバケットに分割することで、フェレール図をデモンストレーションできます。次のように 20 列 x 3 行のグリッドから始めます。
12345678901234567890 1****************** 2* 3*
したがって、最初のパーティションは {18, 1, 1} になります。
次に、アイテムをスタックの一番上から次のスロットに移動します。
12345678901234567890 1***************** 2** 3*
新しいパーティションは {17, 2, 1} です。あるスタックから別のスタックにアイテムを移動できます。
12345678901234567890 1**************** 2*** 3*
これで、{16, 3, 1} が得られました。すべての順列を列挙するまでこの方法を続けます ({17, 1, 2} が {17, 2, 1} とは異なるパーティションであるかどうかはあなた次第です)。
この時点から、必要なアルゴリズムの概要を想像できるはずです。つまり、この関数を最初から作成することに挑戦したい場合です。他の人はすでに 効率的な関数をたくさん書きました 問題を簡単に解決するために。