4

アイテムの文字列のリストを指定して、各グループにアイテムがあるグループnに分割したいb(b<=n)i to j (j>=i)

例：言う

List<string> lst=new List<string>(new string[]{"a","b","c","d"});

(したがってn=4)

この機能を提供する機能が

List<List<string>> DivideIntoGroup(List<string> lst, b, i, j)

可能な結果の1つDivideIntoGroup(lst, 3, 1, 2)は

{"a"},
{"b","c"},
{"d"}

DivideIntoGroup 関数はどのように記述すればよいですか?

4

2 に答える 2

4

私は C# の専門家ではないので、純粋に数学的なソリューションを提供します。うまくいけば、それをあなたの言語に翻訳できると思います。

基本的に、タスクは 2 つの部分で構成されています。b グループ i から j 個の要素をそれぞれ選択することと、ランダム性です。2 つ目は簡単なはずです。最初に要素をランダムにシャッフルしてから、グループ分割を行います。興味深い部分に取り掛かりましょう。

各要素をb含むグループでn個の要素を分割する方法は? 簡単な解決策は、最初のグループ、次に 2 番目などの要素の数の間で乱数を取得することです。ただし、そうすると、要素番号を持つ最後のグループが残らないという保証はありません。との間ではありません。また、そのようなソリューションは純粋なランダム配布を行っていません。ijijij

正しいアプローチは、最初のグループの要素の数を取得することです。要素をできるだけ多く取る場合のグループ分割全体の解の確率を考慮しますtask(n, b, i, j)。最初のグループの要素task(n-k, b-1, i, j)を取ると仮定した場合。k解の数だけを計算できる場合は、各 k をそれぞれの確率で取得し、最初のグループに対して k のランダム サンプリングを行い、次に 2 番目のグループなどを行うことができます...

では、問題は次のとおりです。 にはいくつの解がありtask(n, b, i, j)ますか? これらの数値は、再帰を使用して簡単に見つけることtask(n, b, i, j) = sum(k=i to j) task(n-k, b - 1, i, j)ができることに注意してください (値を複数回計算する必要がないように、動的最適化を使用してください)。

PS: 解決策の数には閉じた形式の解決策があるかもしれませんが、すぐに理解することはできず、n * b比較的小さく保たれている限り (< 10^6) 再帰的な解決策が機能するはずです。

編集
PS2: 実際には、の数値はtask(n, b, i, j)非常に速くかなり大きくなる可能性があるため、大きな整数の使用を検討してください。

于 2012-09-16T10:34:24.740 に答える
0

私が解決策として行うことはそうです、これはもちろん疑似コードです：

func( n, b, i, j )
{
    if(n == 0)
        return //finished
    if(i>j or i>min(j,n))
        return //no solution possible down this path
    out = choose_random_between (i , min(j,n)) 
    current_ave_of_cells_per_group = ( (n - out) / (b - 1) )
    if current_ave_of_cells_per_group < i
        func ( n, b, i, min(out-1,n) )
    else if current_ave_of_cells_per_group > j
        func ( n, b, out+1, min(j,n) )
    else    
        **form the group consisting of 'out' numbers**
        func ( n-out, b-1, i, min(j,n-out) )
}
于 2012-09-16T11:05:53.113 に答える