組み合わせ論:要素を並べ替えたまま、100 個の要素からなるグループを 10 個構築する

StackOverflow https://stackoverflow.com/questions/1351828

  •  20-09-2019
  •  | 
  •  

質問

組み合わせ論に関する問題があります。残念ながら抽象的には説明できないので、物語として説明してみます。:)

問題：

  1. 校庭には100人の子供たちがいます。
  2. 値が 100 ～ 199cm であると仮定すると、それらはすべて固有の高さを持ちます。
  3. それぞれが 1 ～ 99 人の子で構成される 10 個のグループを作成するとします。
  4. 子供を身長順に並べ替える必要があるときに、どのようにしてすべてのグループを作成できるでしょうか?
  5. 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} とは異なるパーティションであるかどうかはあなた次第です)。

この時点から、必要なアルゴリズムの概要を想像できるはずです。つまり、この関数を最初から作成することに挑戦したい場合です。他の人はすでに 効率的な関数をたくさん書きました 問題を簡単に解決するために。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top