0

我有一个正在处理的个人项目,但我有一个似乎无法解决的问题(好吧,我无法快速解决)。

假设我有一组x[1..|x|]人,一组x元素。

我想创建 x 个组(组号i用于 person number i),并且在每个组中都有y不同的元素。

例如:如果我有 10 个人和 10 个元素,并且我希望每个组都有 2 个元素:

|   0   |1  |2  |3  |4  |5  |6  |7  |8  |9  |
|___________________________________________|
|   7   |4  |0  |6  |2  |8  |3  |1  |9  |5  |
|   6   |9  |5  |8  |7  |0  |2  |3  |1  |4  |

顶行代表人(0..9)
每个人下面的两个数字表示他有哪些元素。
注意:每个元素只出现两次(不多也不少)。
还要注意 person numberi不能有元素 number i
例如:人号 3 不能有元素号 3。

我的问题是如何(快速)创建这些组。
到目前为止,我发现的最佳解决方案是创建一个包含x列和y行的矩阵;
取一个 size 的数组x,将其随机播放,然后查看是否无法将其插入矩阵。如果可以,请移至下一行;如果我不能再次洗牌,看看现在是否可以插入。

问题是,即使数量很少(1000 人/元素,每组 50 个元素),代码也很慢。
问题在于洗牌,当它试图找到与行(~13)的匹配时,它需要重新洗牌很多次,直到找到可以放在矩阵内的行。

有谁知道如何快速完成这件事?任何想法都会受到欢迎!!

谢谢。

4

2 回答 2

0

用数学术语来说,你想要的是生成一个没有固定点的随机排列。这被称为一个这被称为一个紊乱(有关更多详细信息,包括随机排列成为紊乱的概率,请参见此处)。如果你用谷歌搜索“生成随机紊乱”或类似的东西,你会发现几个实现。

于 2012-09-17T18:24:27.943 回答
0

您可以遍历人员,将每个该数字的 y 元素放入未满的随机组中。只需有一个包含空组的数组,并在它们填满时将其删除,当然还可以从随机选择中排除当前组。

于 2012-09-17T17:38:58.680 回答