c# - 将字符串列表随机分组

Question

给定一个字符串列表 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 函数？

Answer 1

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

基本上，您的任务由两个独立的部分组成:分别选择 b 组 i 到 j 元素，以及随机性。第二个应该很简单——最初只是随机洗牌，然后进行分组。让我们开始讨论有趣的部分:

如何拆分b组中的n个元素，每组包含i到j个元素？一个直接的解决方案是取 i 和 j 之间的随机数作为第一组元素的数量，然后是第二组等等。但是，不能保证，这样一来，您将不会剩下元素编号不在 i 和 j 之间的最后一组。此外，此类解决方案并未进行纯随机分布。

正确的方法是获取第一组元素的数量，考虑到当你采用尽可能多的元素时整体组 split 的解决方案的概率 - 你基本上对 的整体解决方案有多少感兴趣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) 中的数字可能会很快变得非常大，因此请考虑使用大整数。