用于分隔相同类型的项的算法

Question

我有一个元素列表,每个元素都用类型标识,我需要重新排序列表以最大化相同类型元素之间的最小距离.

该套装很小(10至30件),因此性能并不重要.

每种类型的物品数量或类型数量没有限制,数据可以被认为是随机的.

例如,如果我有一个列表:

• A项5项
• B项3项
• 2件C
• D项2项
• 1项E
• 1项.F

我想产生类似: A,B,C,A,D,F,B,A,E,C,A,D,B,A

• A出现之间至少有2项
• B在出现之间至少有4个项目
• C在出现之间有6个项目
• D在出现之间有6个项目

是否有算法来实现这一目标？

-Update-

在交换了一些评论后,我得出了一个次要目标的定义:

• 主要目标:最大化相同类型元素之间的最小距离,仅考虑距离较小的类型.
• 次要目标:最大化每种类型的元素之间的最小距离.IE:如果组合增加某种类型的最小距离而不减少其他类型,则选择它.

- 更新2-

关于答案.有很多有用的答案,虽然没有一个是两个目标的解决方案,特别是第二个是棘手的.

关于答案的一些想法:

• PengOne:听起来很不错,虽然它没有提供具体的实现,但并不总能根据第二个目标获得最佳结果.
• Evgeny Kluev:为主要目标提供具体实施,但根据次要目标不会产生最佳结果.
• tobias_k:我喜欢随机方法,它并不总能带来最好的结果,但它是一个很好的近似和成本效益.

我试过叶夫根Kluev,回溯,和tobias_k式的组合,但它需要太多的时间来得到结果.

最后,至少对于我的问题,我认为tobias_k是最合适的算法,因为它的简单性和及时的良好结果.可能使用模拟退火可以改善它.

Answer 1

首先,您还没有明确定义的优化问题.如果你想最大化两个相同类型的项目之间的最小距离,那就很好了.如果你想最大化两个A之间以及两个B和......之间以及两个Z之间的最小距离,那么这个定义并不明确.您如何比较两种解决方案:

1. A至少相隔4分,B分别至少4分,C分别至少2分
2. A至少相距3分,B分别至少3分,C分别至少4分

你需要一个明确定义的"好"度量(或者更确切地说,"更好").我现在假设该措施是:最大化同一项目中任意两个之间的最小距离.

这是一种算法,它实现了最小距离,ceiling(N/n(A))其中where N是项目总数,并且n(A)是实例的项目数A,假设A是最多的.

• 在A1, A2, ... , Ak哪里订购商品类型n(Ai) >= n(A{i+1}).
• 将列表初始化L为空.
• 为j从k到1,分发类型的项目Ak尽可能均匀可能的L.

示例:给定问题中的分布,算法产生:

F
E, F
D, E, D, F
D, C, E, D, C, F
B, D, C, E, B, D, C, F, B
A, B, D, A, C, E, A, B, D, A, C, F, A, B

Answer 2

这听起来是一个有趣的问题，所以我尝试了一下。这是我用 Python 完成的超级简单的随机方法：

def optimize(items, quality_function, stop=1000):
    no_improvement = 0
    best = 0
    while no_improvement < stop:
        i = random.randint(0, len(items)-1)
        j = random.randint(0, len(items)-1)
        copy = items[::]
        copy[i], copy[j] = copy[j], copy[i]
        q = quality_function(copy)
        if q > best:
            items, best = copy, q
            no_improvement = 0
        else:
            no_improvement += 1
    return items

正如评论中已经讨论的那样，真正棘手的部分是质量函数，它作为参数传递给优化器。经过一番尝试后，我想出了一个几乎总是能产生最佳结果的方法。感谢pmoleri指出如何提高效率。

def quality_maxmindist(items):
    s = 0
    for item in set(items):
        indcs = [i for i in range(len(items)) if items[i] == item]
        if len(indcs) > 1:
            s += sum(1./(indcs[i+1] - indcs[i]) for i in range(len(indcs)-1))
    return 1./s

这里有一些随机结果：

>>> print optimize(items, quality_maxmindist)
['A', 'B', 'C', 'A', 'D', 'E', 'A', 'B', 'F', 'C', 'A', 'D', 'B', 'A']

请注意，通过另一个质量函数，相同的优化器可以用于不同的列表重新排列任务，例如作为（相当愚蠢的）随机排序器。