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)

可能的结果之一DivideIntoGroup(lst, 3, 1, 2)是

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

我应该如何编写 DivideIntoGroup 函数？

4

2 回答 2

4

我不是 C# 专家，所以我会给你一个纯粹的数学解决方案，希望你能用你的语言翻译它。

基本上，您的任务由两个独立的部分组成：选择 b 组 i 到 j 个元素，以及随机性。第二个应该很容易 - 最初只是随机打乱元素，然后进行组拆分。让我们来看看有趣的部分：

如何将 n 个元素分成b包含每个元素的组？一个直接的解决方案是在第一组的元素数量之间取随机数，然后是第二组，等等。但是，不能保证这样做你不会留下最后一组元素编号不在和之间。这种解决方案也不是纯粹的随机分布。ijijij

正确的方法是获取第一组的元素数量，当您采用尽可能多的元素时，尊重整体组分裂的解决方案的概率 - 您基本上感兴趣的是总体上有多少解决方案task(n, b, i, j)以及存在多少解决方案task(n-k, b-1, i, j)如果我们假设我们k在第一组中取元素。如果我们能够仅计算解决方案的数量，您可以取每个 k 及其各自的概率，并对第一组的 k 进行随机抽样，然后是第二组，依此类推......

所以现在的问题是：有多少解决方案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 回答