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

问题描述

我有元素的列表，每一个标记有型，我需要重新排序相同类型的元素之间的列表为最大化在最小距离。

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.

这组小（10〜30项），因此性能是不是真的很重要。

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项A的
• 3项的B
• 2项的C
• 2项的D
的E
• 1个项目
的F
• 1个项目

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

我想产生类似： A ， B ， C ， A ， D ， F ， B ， A ，电子， C ， A ， D ， B ， A

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

• 系统至少有2项事件再度发生之间
• B有至少4项事件再度发生之间
• C有6项事件再度发生之间
• D有6项事件再度发生之间

有一个算法来实现这一目标？

Is there an algorithm to achieve this?

- 更新 -

交换一些意见后，我来到了一个次要目标的定义：

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 的：听起来不错，但它并没有提供一个具体的实现，而不是一味按照第二个目标导致最好的结果
• 的叶夫根尼·Kluev 的：提供一个具体实现的主要目标，但根据第二个目标也不会导致最好的结果
• tobias_k：我喜欢随机的方式，它并不总是带来最好的结果，但它是一个很好的近似和具有成本效益

• 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.

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

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

最后，至少对于我的问题，我认为tobias_k是最适当的算法，它的简单和及时的好成绩。也许，这可以用改进的模拟退火的。

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.

推荐答案

这听起来像一个有趣的问题，所以我只是给它一个尝试。这是我的超级简单随机的方法，在Python中完成的：

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

由于在评论中已经讨论过，真正棘手的部分是质量功能，作为参数传递给优化。经过一番努力，我想出了一个几乎总是产生最佳的效果。感谢到的 pmoleri 的，用于指出如何使这一大堆更有效率。

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屋！