从源元素生成具有最小保证距离的排列

Question

给定一个包含n个独特元素的序列a，我想创建一个序列b，它是a的随机排列，并且序列b加到序列a后至少有指定的最小距离d在序列中任意两个重复元素之间。

例如，如果a = [1,2,3]，且d=2，则以下排列之一：

a         b
[1, 2, 3] (1, 2, 3) mindist = 3
[1, 2, 3] (1, 3, 2) mindist = 2
[1, 2, 3] (2, 1, 3) mindist = 2
[1, 2, 3] (2, 3, 1) mindist = 2
[1, 2, 3] (3, 1, 2) mindist = 1
[1, 2, 3] (3, 2, 1) mindist = 1

只有前四个值可以赋给b，因为最后两个值的最小距离为1 < d。

我编写了以下实现：

import random
n = 10
alist = list(range(n))

blist = alist[:]

d = n//2

avail_indices = list(range(n))
for a_ind, a_val in enumerate(reversed(alist)):
  min_ind = max(d - a_ind - 1, 0)
  new_ind = random.choice(avail_indices[min_ind:])
  avail_indices.remove(new_ind)
  blist[new_ind] = a_val
print(alist, blist)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [1, 3, 2, 8, 5, 6, 4, 0, 9, 7]

但我认为这是一个 n^2 的时间复杂度（不完全确定）。下面是当 d = n//2 时，所需时间随着增加的 n 呈现的图表：

是否有可能做得比这更好？

- jippyjoe4

Answer 1

是的，你的实现是 O(n^2) 的。

你可以采用Fisher-Yates 洗牌算法来解决这个问题。你需要从数组开头到结尾进行操作，将最终的值放入剩余位置中。

关键在于，在完全洗牌时，你可以将任何元素放在开头，但你只能从符合距离条件的索引处开始放置。

以下是一个实现示例。

import random

def distance_permutation (orig, d):
    answer = orig.copy()
    for i in range(len(orig)):
        choice = random.randrange(i, min(len(orig), len(orig) + i - d + 1))
        if i < choice:
            (answer[i], answer[choice]) = (answer[choice], answer[i])
    return answer


n = 10
x = list(range(n))
print(x, distance_permutation(x, n//2))

- btilly

---

@kcsquared 你是对的，我刚刚修复了它。抱歉造成困扰。 - btilly