2

我正在寻找一种算法来随机化一组具有 length 的项目n，其中每个项目可能有多个（1 到m）。另一个限制是同一项目可能不会出现k在前一个项目中。

您可能会假设n它远低于 100，并且总是有一个解决方案，即m很小k。如果有帮助，您还可以将输入更改为 <item, frequency> 对列表。

为了提供一些背景信息，假设我在游戏中生成任务并且有一组目标可供选择。有些目标可能会出现多次（例如“杀死老板”），但不应彼此靠近，因此简单地洗牌“袋子”是不好的。

我可以对列表进行洗牌，然后在跟踪项目间隔的同时对其进行迭代，如果测试失败，则从新的洗牌开始，但我正在寻找一种更优雅的解决方案，它也应该是紧凑、实用且易于实现的，例如C、C++ 或 JavaScript。换句话说，它不应该依赖于我可能不理解或很难实现的特殊语言特性或标准库函数。但是，您可以假设最常见的列表操作（例如排序和混洗）可用。

4

1 回答 1

1

如果您想要一组有效结果的统一概率，我的直觉是您提出的拒绝方案（如果安排不好，则重新排序然后重新启动）将是最容易正确编码、理解、阅读和维护的可能相当接近最快的，假设这些数字使得大多数排列都是有效的。

不过，这是另一种简单的方法，它基于贪婪地选择有效值并希望你不要把自己搞垮。如果有许多无效排列（高m和k），则根本不能保证找到解决方案。

shuffled = list of length n
not_inserted = {0, 1, ..., n-1}
for each item i, frequency m_i, nearness constraint k_i:
    valid = not_inserted
    do m_i times:
        choose an index j from valid
        shuffled[j] = i
        not_inserted.remove(j)
        valid.remove(j-k_i, j-k_i+1, ..., j, ..., j+k_i)

如果valid为空，则您构建的部分解决方案很糟糕，您可能必须重新启动。我猜如果你按照递减的顺序循环，失败的可能性就会降低m_i。

与排序/拒绝方法相比，我不确定这种方法失败的频率有多高（实现并运行一些数字会很有趣......）。我猜想在k中等高的情况下它可能会更快，但通常更慢，因为洗牌对于n << 100.

于 2012-07-27T08:45:52.223 回答