生成“近乎有序”或“k有序”列表的算法？

Question

我想生成一些测试数据来测试一个函数，该函数将“k个排序”列表（其中每个元素的位置最多与其正确排序位置相差k个位置）合并为单个完全排序的列表。我有一个可行的方法，但我不确定它有多随机化，而且我觉得应该有一种更简单/更优雅的方法来做到这一点。我的当前方法如下：

1. 生成n个随机元素，并配对一个整数索引。
2. 对随机元素进行排序。
3. 将每个元素的配对索引设置为其排序位置。
4. 向后遍历元素，将每个元素与列表中距离1到k个位置之间的另一个元素交换。仅在目标元素的配对索引为其当前索引时才与目标元素交换（这避免了交换已经不在正确位置并将其移动超过k个位置的元素）。
5. 将扰动的元素复制到另一个列表中。

就像我说的那样，这个方法是有效的，但我对替代/更好的方法感兴趣。

- mattnewport

---

你需要输出完全排序（0排序），还是仅仅K排序？ - Aaron McDaid

输出旨在进行k排序（用作将k排序列表合并的算法的测试输入）。 - mattnewport

我刚意识到我的输入和输出搞混了。你将创建许多列表，每个列表都是k排序的。你正在测试的算法将把这些列表合并成一个列表。那个（单一的、大的）合并列表将是0排序还是k排序？ - Aaron McDaid

我想要测试的算法旨在生成完全排序的列表，但这对于本问题的目的并不重要。我只想为它生成适当的k排序测试输入。 - mattnewport

Answer 1

我认为您可以用随机整数填充一个数组，然后在其上运行快速排序并使用自定义的停止条件。

如果在某个快速排序递归中，您的start和end索引相差不到k，则返回而不是继续递归。

由于快速排序的工作原理，start..end区间内的每个数字都属于该区域的某个位置；最坏的情况是，array[start]可能真正应该在真正排序顺序中的array[end]（或反之亦然）。因此，确保start和end之间的距离不超过k就足够了。

- Gabe Moothart

---

但这意味着范围中间的值将少于 k，我认为这不会很均匀。 - augurar

Answer 2

你可以生成随机数数组，然后像希尔排序一样对其进行h排序，但当 h 小于 k 时，不要进行最后几个排序步骤。

- Evgeny Lazin

Answer 3

步骤1：随机排列长度为k的不相交段。（例如，从1到K，从k+1到2k...）

步骤2：通过交换有条件地再次排列（以确保它们不会破坏k排序的假设（1+t到k+t，k+1+t到1+2k+t...），其中t是1到k之间的数字（最好是k/2）

可能会多次重复步骤2，并使用不同的t。

- ElKamina

Answer 4

如果我理解问题正确，您想要一个算法来随机选择一个长度为n的单个k排序列表，从所有k排序列表的宇宙U中均匀选择。 （然后您将运行此算法m次以生成m个列表作为输入测试数据。）

第一步是计算它们的数量。 U的大小是多少？ |U|

下一步是枚举它们。 创建任何一对一映射F，将整数(1,2,...,|U|)和长度为n的k排序列表相互映射。

然后，在1到|U|之间随机选择一个整数x，然后应用F(x)以获取列表。

- Andrew Tomazos

---

这只是描述有限集上的统一选择是什么，并不会导致有用的算法。 - augurar