分离相同类型项目的算法 [英] Algorithm to separate items of the same type

问题描述

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

集合很小(10 到 30 个项目)，所以性能并不重要.

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

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

• 5项A
• 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 个项目

有没有算法可以实现这一点?

-更新-

在交换了一些意见之后，我得出了次要目标的定义:

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

-更新 2-

关于答案.有很多有用的答案，尽管没有一个是针对这两个目标的解决方案，尤其是第二个很棘手.

关于答案的一些想法:

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

我尝试了 Evgeny Kluev、回溯和 tobias_k 公式的组合，但需要太多时间才能得到结果.

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

解决方案

这听起来很有趣，所以我就试了一下.这是我用 Python 完成的超级简单的随机方法:

def optimize(items, quality_function, stop=1000):no_improvement = 0最好 = 0而 no_improvement <停止:i = random.randint(0, len(items)-1)j = random.randint(0, len(items)-1)复制 = 物品[::]复制[i]，复制[j] = 复制[j]，复制[i]q = quality_function(复制)如果 q >最好的事物:项目，最佳 = 副本，qno_improvement = 0别的:no_improvement += 1退换货品

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

def quality_maxmindist(items):s = 0对于集合中的项目(项目):indcs = [i for i in range(len(items)) if items[i] == item]如果 len(indcs) >1:s += sum(1./(indcs[i+1] - indcs[i]) for i in range(len(indcs)-1))返回 1./s

这里有一些随机结果:

<预><代码>>>>打印优化(项目，quality_maxmindist)['A', 'B', 'C', 'A', 'D', 'E', 'A', 'B', 'F', 'C', 'A', 'D', 'B', 'A']

请注意，通过另一个质量函数，相同的优化器可以用于不同的列表重排任务，例如作为(相当愚蠢的)随机分拣机.

I have a list of elements, each one identified with a type, I need to reorder the list to maximize the minimum distance between elements of the same type.

The set is small (10 to 30 items), so performance is not really important.

There's no limit about the quantity of items per type or quantity of types, the data can be considered random.

For example, if I have a list of:

• 5 items of A
• 3 items of B
• 2 items of C
• 2 items of D
• 1 item of E
• 1 item of F

I would like to produce something like: A, B, C, A, D, F, B, A, E, C, A, D, B, A

• A has at least 2 items between occurences
• B has at least 4 items between occurences
• C has 6 items between occurences
• D has 6 items between occurences

Is there an algorithm to achieve this?

-Update-

After exchanging some comments, I came to a definition of a secondary goal:

• main goal: maximize the minimum distance between elements of the same type, considering only the type(s) with less distance.
• secondary goal: maximize the minimum distance between elements on every type. IE: if a combination increases the minimum distance of a certain type without decreasing other, then choose it.

-Update 2-

About the answers. There were a lot of useful answers, although none is a solution for both goals, specially the second one which is tricky.

Some thoughts about the answers:

• PengOne: Sounds good, although it doesn't provide a concrete implementation, and not always leads to the best result according to the second goal.
• Evgeny Kluev: Provides a concrete implementation to the main goal, but it doesn't lead to the best result according to the secondary goal.
• tobias_k: I liked the random approach, it doesn't always lead to the best result, but it's a good approximation and cost effective.

I tried a combination of Evgeny Kluev, backtracking, and tobias_k formula, but it needed too much time to get the result.

Finally, at least for my problem, I considered tobias_k to be the most adequate algorithm, for its simplicity and good results in a timely fashion. Probably, it could be improved using Simulated annealing.

解决方案

This sounded like an interesting problem, so I just gave it a try. Here's my super-simplistic randomized approach, done in 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

As already discussed in the comments, the really tricky part is the quality function, passed as a parameter to the optimizer. After some trying I came up with one that almost always yields optimal results. Thank to pmoleri, for pointing out how to make this a whole lot more efficient.

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

And here some random result:

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

Note that, passing another quality function, the same optimizer could be used for different list-rearrangement tasks, e.g. as a (rather silly) randomized sorter.

这篇关于分离相同类型项目的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！