如何在没有随机性的情况下对列表进行洗牌，并保证一部分元素最终会出现在一侧？

Question

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

例子： { 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 } 等

难度： 算法不应该使用随机数来混合内容，应该是一个迭代的过程。 所以 Fisher-Yates 已经出局了。

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

我认为您正在寻找一种算法：
* 可用于向用户显示看起来像洗牌的迭代过程
* 最终将原始集合分为 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 那样提供有效的、统计上良好的洗牌，但确实可以在屏幕上提供美观的混合效果。