3

给定一个元素列表，是否存在洗牌算法来保证最终选定的一半部分位于一侧，而其余部分位于另一侧？

示例：{ 4, 3, 10, 7, 2, 9, 6, 8, 1, 5 }

鉴于上面的集合，我希望有一个混合算法，最终将标记的向左移动，即使算法本身不知道什么是“标记”和没有“标记”。

   { 4, 3, 10, 7, 2, 9, 6, 8, 1, 5 }
     X X X X X

可接受的结果是：
   { 4, 10, 9, 6, 1, 3, 7, 2, 8, 5 }
   { 1, 9, 10, 4, 6, 2, 8, 5, 7, 3 }
   { 1, 4, 9, 10, 6, 3, 7, 5, 8, 2 } 等

难点：算法不应该使用随机数来混合内容，它应该是一个迭代过程。所以费舍尔-耶茨出局了。

4

4 回答 4

4

将您的列表分成两个列表 - 已标记和未标记。洗牌两个子列表，将标记的放在一侧，将未标记的放在另一侧。现在你可以使用任何你想要的洗牌算法。

于 2010-07-21T13:54:04.093 回答
1

会std::next_permutation()是你想要的吗？（因为它创建了所有可能的排列，它最终也会把标记的一次放在左边。）

于 2010-07-21T13:51:39.417 回答
0

我认为您正在寻找一种算法： * 可用于向用户显示类似于改组的迭代过程 * 最终将原始集合分成 2 个（预选）组，但在每个组中随机排序

在我看来，一些简单的东西可能适合您考虑您的十个数字并使用该算法的组标记/未标记的术语：

1. Randomly select two members of the set
2. if swapping these two members would result in a marked number 
     being moved into positions 1-5 then forget about this swap and start again
3. Swap these elements
4. Check if positions 1-5 have ONLY marked elements, 
     if so you are done, otherwise start again

这并没有像 Fisher-Yates 那样提供有效的统计上良好的洗牌，但确实让您在屏幕上看起来很漂亮。

于 2010-07-21T14:15:03.047 回答
0

类似的东西next_permutation可以完成这项工作，并且（最终）类似 bogo sort 的东西也可以。两者最终都会产生所有可能的排列，包括您认为可以接受的所有排列（以及一些您不接受的任意数字）。

Bogo 排序表明您的：“算法不应该使用随机数来混合内容，它应该是一个迭代过程。所以 Fisher-Yates 出局了。” 是错误的二分法。Bogo 排序随机混合并且是迭代的。

于 2010-07-21T13:58:49.067 回答