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

Question

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

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

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

Answer 1

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

如果在特定的快速排序递归中，您的

start

和

end

索引小于

k

，那么只需返回而不是继续递归。

由于快速排序的工作原理，

start..end

区间中的每个数字都属于该区域的某个位置；最坏的情况是

array[start]

可能确实属于真正排序的

array[end]

（反之亦然）。因此，确保

start

和

end

之间的距离不超过

k

就足够了。

Answer 2

您可以生成随机数数组，然后像shellsort中那样对它进行h排序，但是当h小于k时，没有最后的排序步骤。

Answer 3

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

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

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

Answer 4

如果我理解这个问题，你想要一个算法随机选择一个长度为

k

的单个

n

排序列表，从所有长度为

U

的

k

排序列表的宇宙

n

中统一选择。 （然后，您将运行该算法

m

次以生成

m

列表作为输入测试数据。）

第一步是数数。

U

的尺寸是多少？

|U|

下一步是枚举它们。在整数

F

和长度为

(1,2,...,|U|)

的

k

排序列表之间创建任意一对一映射

n

。

然后随机选择一个介于 1 和

x

（含）之间的整数

|U|

，然后应用

F(x)

来获取列表。

Answer 5

您也可以将此问题建模为完美匹配问题。 您有一个二部图 G=(S,T,E)，两个类中都有 n 个节点。排序数组是类 S，k 排序排列将是 T。 在匹配中使用 (i,j) 边意味着排序数组中的第 i 个元素将转到 k 排序数组中的第 j 个索引。

在G中，如果距离(i,j)至多为k，则(i,j)可以是边。 我们还需要一个随机 c 目标函数，这将确保完美匹配是随机的。

之后我们可以使用LP求解器来得到解。

这是一个Python实现：

import mip
import random

def perfect_matching(data: list[int], k:int):
    def k_range(i, k):
        return range( max(i-k, 0), min(i+k+1, len(data)) )

    # create model
    model = mip.Model("Matching")
    N = range(len(data))

    # add variables: x[i, j] is the (i, j) edge 
    x = [ [ model.add_var( name=f'x_{i}_{j}', var_type=mip.BINARY) for j in 
    k_range(i,k) ] for i in N ]

    # constraints: 
    for i in N:
        # For every i in S
        model += mip.xsum( x[i][j] for j in range(len(x[i])) ) == 1

    for j in N:
        # For every j in T
        model += mip.xsum( x[i][j-max(0,i-k)] for i in k_range(j,k) ) == 1

    # random objective function
    c = [ [ random.uniform(0,1) if i!=j else random.uniform(0,1)/(2*k+1) 
    for j in k_range(i,k) ] for i in N ]

    # solve the model
    model.verbose = 0
    model.objective = mip.maximize(mip.xsum(c[i][j] * x[i][j] for j in 
    range(len(x[i])) for i in N))
    model.optimize()

    assert (
        model.status == mip.OptimizationStatus.OPTIMAL
    ), f"could not solve problem to optimality (status= {model.status})"

    # return the solution
    permutation = [x[i][j].name for i in N for j in range(len(x[i])) if 
    x[i][j].x > 0.9]

    shuffled_data = [data[int(permutation[i].split('_')[-1])] for i in N]
    return shuffled_data