algorithm - 将两个列表与元素之间的最小距离组合起来

Question

我必须像这样列出:

a = ["1a","2a","3a","4a","5a","6a","7a","8a","9a","10a","11a","12a","13a","14a"] 
b = ["1b","2b","3b","4b","5b","6b","7b","8b","9b","10b","11b","12b","13b","14b"]

我想要的是将它们组合起来，这样 a 中的元素与其对应的元素之间至少有 n 个元素的差异b。

例如，如果我的 n 是 10，“3a”在位置 3，“3b”在位置 5，这不是解决方案，因为距离只有 2在这些对应元素之间。

我已经通过暴力方法解决了这个问题，达到了我想要的目的:将两个数组的并集打乱，看看是否满足约束；如果不是，再次洗牌等等......不用说，对于 14 个元素的数组，有时需要 5 到 10 秒的计算才能产生最小距离为 10 的解决方案。尽管这对我来说还可以寻找，我很好奇如何以更优化的方式解决这个问题。

我目前正在使用 Python，但我非常欢迎使用任何语言(或伪代码)编写的代码。

编辑:这个问题的上下文有点像问卷调查，预计大约有 100 名参与者参与。因此，我不一定对所有感兴趣解决方案，而是类似于前 100 个的解决方案。

谢谢。

Answer 1

对于您的特定场景，您可以使用随机方法——尽管不像您已经尝试过的那样随机。像这样:

1. 从两个列表中的项目的随机排列开始
2. 通过创建另一个的副本并随机交换两个项目来创建新的排列
3. 测量排列的质量，例如，每对相关项目的距离之和，或此类距离的最小值
4. 如果新排列的质量优于原始排列，保留新排列，否则丢弃新排列并继续原始排列
5. 从 2. 开始重复，直到每个距离至少为 10 或直到多次迭代后质量没有提高

在每次迭代中对整个列表进行洗牌的区别(如在您的方法中)是，在每次迭代中，排列只能变得更好，直到满意的解决方案是找到了。

每次运行此算法，结果都会略有不同，因此您可以针对 100 种不同的解决方案运行 100 次。当然，此算法不能保证找到解决方案(更不用说所有此类解决方案)，但它应该足够快，以便您可以在失败时重新启动它。

在 Python 中，这可能看起来像这样(稍微简化，但仍然有效):

def shuffle(A, B):
    # original positions, i.e. types of questions
    kind = dict([(item, i) for i, item in list(enumerate(A)) + list(enumerate(B))])

    # get positions of elements of kinds, and return sum of their distances
    def quality(perm):
        pos = dict([(kind[item], i) for i, item in enumerate(perm)])
        return sum(abs(pos[kind[item]] - i) for i, item in enumerate(perm))

    # initial permutation and quality
    current = A + B
    random.shuffle(current)
    best = quality(current)

    # improve upon initial permutation by randomly swapping items
    for g in range(1000):
        i = random.randint(0, len(current)-1)
        j = random.randint(0, len(current)-1)
        copy = current[:]
        copy[i], copy[j] = copy[j], copy[i]
        q = quality(copy)
        if q > best:
            current, best = copy, q

    return current

print shuffle(a, b) 的示例输出:

['14b', '2a', '13b', '3a', '9b', '4a', '6a', '1a', '8a', '5b', '12b', '11a', '10b', '7b', '4b', '11b', '5a', '7a', '8b', '12a', '13a', '14a', '1b', '2b', '3b', '6b', '10a', '9a']