在不同数组中查找“最常见元素”的算法

I have for example 5 arrays with some inserted elements (numbers):

我有5个数组,其中包含一些插入的元素(数字):

1,4,8,10
1,2,3,4,11,15
2,4,20,21
2,30

1,4,8,10 1,2,3,4,11,15 2,4,20,21 2,30

I need to find most common elements in those arrays and every element should go all the way till the end (see example below). In this example that would be the bold combination (or the same one but with "30" on the end, it's the "same") because it contains the smallest number of different elements (only two, 4 and 2/30).

我需要在这些数组中找到最常见的元素,并且每个元素都应该一直持续到最后(参见下面的示例)。在这个例子中,它是粗体组合(或者是相同的一个,但最后是“30”,它是“相同的”)因为它包含最少数量的不同元素(只有两个,4和2/30)。

This combination (see below) isn't good because if I have for ex. "4" it must "go" till it ends (next array mustn't contain "4" at all). So combination must go all the way till the end.

这种组合(见下文)并不好,因为如果我有前任。 “4”它必须“去”直到它结束(下一个数组必须完全不包含“4”)。所以组合必须一直持续到最后。

1,4,8,10
1,2,3,4,11,15
2,4,20,21
2,30

1,4,8,10 1,2,3,4,11,15 2,4,20,21 2,30

EDIT2: OR

1,4,8,10
1,2,3,4,11,15
2,4,20,21
2,30

1,4,8,10 1,2,3,4,11,15 2,4,20,21 2,30

OR anything else is NOT good.

或其他任何东西都不好。

Is there some algorithm to speed this thing up (if I have thousands of arrays with hundreds of elements in each one)?

有没有一些算法来加速这个事情(如果我有数千个阵列,每个阵列有数百个元素)?

To make it clear - solution must contain lowest number of different elements and the groups (of the same numbers) must be grouped from first - larger ones to the last - smallest ones. So in upper example 4,4,4,2 is better then 4,2,2,2 because in first example group of 4's is larger than group of 2's.

为了说清楚 - 解决方案必须包含最少数量的不同元素,并且必须将组(具有相同数字)从第一个 - 较大的组分组到最后一个 - 最小的元素。因此在上面的示例中,4,4,4,2比4,2,2,2更好,因为在第一个示例中,4的组大于2的组。

EDIT: To be more specific. Solution must contain the smallest number of different elements and those elements must be grouped from first to last. So if I have three arrrays like

编辑:更具体。解决方案必须包含最少数量的不同元素,并且这些元素必须从头到尾分组。所以,如果我有三个arrray像

1,2,3
1,4,5
4,5,6

1,2,3 1,4,5 4,5,6

Solution is 1,1,4 or 1,1,5 or 1,1,6 NOT 2,5,5 because 1's have larger group (two of them) than 2's (only one).

解决方案是1,1,4或1,1,5或1,1,6不是2,5,5,因为1有更大的组(其中两个)而不是2(只有一个)。

Thanks.

EDIT3: I can't be more specific :(

编辑3:我不能更具体:(

EDIT4: @spintheblack 1,1,1,2,4 is the correct solution because number used first time (let's say at position 1) can't be used later (except it's in the SAME group of 1's). I would say that grouping has the "priority"? Also, I didn't mention it (sorry about that) but the numbers in arrays are NOT sorted in any way, I typed it that way in this post because it was easier for me to follow.

EDIT4:@spintheblack 1,1,1,2,4是正确的解决方案,因为第一次使用的数字(假设在位置1)以后不能使用(除了它在1的SAME组中)。我会说分组有“优先级”吗?另外,我没有提到它(对不起),但是数组中的数字没有以任何方式排序,我在这篇文章中这样输入,因为我更容易遵循。

5 个解决方案

#1

I am assuming that "distinct elements" do not have to actually be distinct, they can repeat in the final solution. That is if presented with [1], [2], [1] that the obvious answer [1, 2, 1] is allowed. But we'd count this as having 3 distinct elements.

我假设“不同元素”不必实际上是不同的,它们可以在最终解决方案中重复。如果用[1],[2],[1]表示允许明显的答案[1,2,1]。但我们认为这有3个不同的元素。

If so, then here is a Python solution:

如果是这样,那么这是一个Python解决方案:

def find_best_run (first_array, *argv):
    # initialize data structures.
    this_array_best_run = {}
    for x in first_array:
        this_array_best_run[x] = (1, (1,), (x,))

    for this_array in argv:
        # find the best runs ending at each value in this_array
        last_array_best_run = this_array_best_run
        this_array_best_run = {}

        for x in this_array:
            for (y, pattern) in last_array_best_run.iteritems():
                (distinct_count, lengths, elements) = pattern
                if x == y:
                    lengths = tuple(lengths[:-1] + (lengths[-1] + 1,))
                else :
                    distinct_count += 1
                    lengths = tuple(lengths + (1,))
                    elements = tuple(elements + (x,))

                if x not in this_array_best_run:
                    this_array_best_run[x] = (distinct_count, lengths, elements)
                else:
                    (prev_count, prev_lengths, prev_elements) = this_array_best_run[x]
                    if distinct_count < prev_count or prev_lengths < lengths:
                        this_array_best_run[x] = (distinct_count, lengths, elements)

    # find the best overall run
    best_count = len(argv) + 10 # Needs to be bigger than any possible answer.
    for (distinct_count, lengths, elements) in this_array_best_run.itervalues():
        if distinct_count < best_count:
            best_count = distinct_count
            best_lengths = lengths
            best_elements = elements
        elif distinct_count == best_count and best_lengths < lengths:
            best_count = distinct_count
            best_lengths = lengths
            best_elements = elements

    # convert it into a more normal representation.                
    answer = []
    for (length, element) in zip(best_lengths, elements):
        answer.extend([element] * length)

    return answer

# example
print find_best_run(
    [1,4,8,10],
    [1,2,3,4,11,15],
    [2,4,20,21],
    [2,30]) # prints [4, 4, 4, 30]

Here is an explanation. The ...this_run dictionaries have keys which are elements in the current array, and they have values which are tuples (distinct_count, lengths, elements). We are trying to minimize distinct_count, then maximize lengths (lengths is a tuple, so this will prefer the element with the largest value in the first spot) and are tracking elements for the end. At each step I construct all possible runs which are a combination of a run up to the previous array with this element next in sequence, and find which ones are best to the current. When I get to the end I pick the best possible overall run, then turn it into a conventional representation and return it.

这是一个解释。 ... this_run词典的键是当前数组中的元素,它们的值是元组(distinct_count,length,elements)。我们试图最小化distinct_count,然后最大化长度(长度是一个元组,所以这将更喜欢第一个点中具有最大值的元素)并且是结束的跟踪元素。在每个步骤中,我构造所有可能的运行,这些运行是前一个数组的运行与下一个顺序的元素的组合,并找出哪些最适合当前。当我到达终点时,我选择最佳的整体运行,然后将其转换为传统表示并返回它。

If you have N arrays of length M, this should take O(N*M*M) time to run.

如果你有N个长度为M的数组,这应该花费O(N * M * M)时间。

#2

Here is the approach you want to take, if arrays is an array that contains each individual array.

如果数组是包含每个单独数组的数组,那么这是您要采用的方法。

1. Starting at i = 0

从i = 0开始

2. current = arrays[i]

current = arrays [i]

3. Loop i from i+1 to len(arrays)-1

循环i从i + 1到len(数组)-1

4. new = current & arrays[i] (set intersection, finds common elements)

new = current&arrays [i](设置交集,查找公共元素)

5. If there are any elements in new, do step 6, otherwise skip to 7

如果new中有任何元素,请执行步骤6,否则跳至7

6. current = new, return to step 3 (continue loop)

current = new,返回步骤3(继续循环)

7. print or yield an element from current, current = arrays[i], return to step 3 (continue loop)

打印或从current,current = arrays [i]中生成一个元素,返回步骤3(继续循环)

Here is a Python implementation:

这是一个Python实现:

def mce(arrays):
  count = 1
  current = set(arrays[0])
  for i in range(1, len(arrays)):
    new = current & set(arrays[i])
    if new:
      count += 1
      current = new
    else:
      print " ".join([str(current.pop())] * count),
      count = 1
      current = set(arrays[i])
  print " ".join([str(current.pop())] * count)

>>> mce([[1, 4, 8, 10], [1, 2, 3, 4, 11, 15], [2, 4, 20, 21], [2, 30]])
4 4 4 2

#3

If all are number lists, and are all sorted, then,

如果所有都是数字列表,并且都已排序,那么,

1. Convert to array of bitmaps.

转换为位图数组。

2. Keep 'AND'ing the bitmaps till you hit zero. The position of the 1 in the previous value indicates the first element.

保持'和'位图直到你达到零。前一个值中1的位置表示第一个元素。

3. Restart step 2 from the next element

从下一个元素重新启动第2步

#4

This has now turned into a graphing problem with a twist.

现在这变成了一个扭曲的图形问题。

The problem is a directed acyclic graph of connections between stops, and the goal is to minimize the number of lines switches when riding on a train/tram.

问题是停靠点之间连接的有向无环图,目标是在乘坐火车/有轨电车时最小化线路开关的数量。

ie. this list of sets:

即。这个集合列表:

1,4,8,10           <-- stop A
1,2,3,4,11,15      <-- stop B
2,4,20,21          <-- stop C
2,30               <-- stop D, destination

He needs to pick lines that are available at his exit stop, and his arrival stop, so for instance, he can't pick 10 from stop A, because 10 does not go to stop B.

他需要选择在他的出口站点可用的线路和他的到达站点,例如,他不能从A站点选择10,因为10不会停止B.

So, this is the set of available lines and the stops they stop on:

所以,这是可用线路的集合以及它们停止的止损:

             A     B     C     D
line 1  -----X-----X-----------------
line 2  -----------X-----X-----X-----
line 3  -----------X-----------------
line 4  -----X-----X-----X-----------
line 8  -----X-----------------------
line 10 -----X-----------------------
line 11 -----------X-----------------
line 15 -----------X-----------------
line 20 -----------------X-----------
line 21 -----------------X-----------
line 30 -----------------------X-----

If we consider that a line under consideration must go between at least 2 consecutive stops, let me highlight the possible choices of lines with equal signs:

如果我们认为正在考虑的线路必须至少连续2次停止,那么让我强调可能选择具有相同符号的线路:

             A     B     C     D
line 1  -----X=====X-----------------
line 2  -----------X=====X=====X-----
line 3  -----------X-----------------
line 4  -----X=====X=====X-----------
line 8  -----X-----------------------
line 10 -----X-----------------------
line 11 -----------X-----------------
line 15 -----------X-----------------
line 20 -----------------X-----------
line 21 -----------------X-----------
line 30 -----------------------X-----

He then needs to pick a way that transports him from A to D, with the minimal number of line switches.

然后他需要选择一种方式将他从A传输到D,并使用最少的线路开关。

Since he explained that he wants the longest rides first, the following sequence seems the best solution:

由于他解释说他想要最长的游乐设施,以下序列似乎是最好的解决方案:

• take line 4 from stop A to stop C, then switch to line 2 from C to D

从停止A到第4行停止C,然后从C到D切换到第2行

Code example:

stops = [
    [1, 4, 8, 10],
    [1,2,3,4,11,15],
    [2,4,20,21],
    [2,30],
]

def calculate_possible_exit_lines(stops):
    """
    only return lines that are available at both exit
    and arrival stops, discard the rest.
    """

    result = []
    for index in range(0, len(stops) - 1):
        lines = []
        for value in stops[index]:
            if value in stops[index + 1]:
                lines.append(value)
        result.append(lines)
    return result

def all_combinations(lines):
    """
    produce all combinations which travel from one end
    of the journey to the other, across available lines.
    """

    if not lines:
        yield []
    else:
        for line in lines[0]:
            for rest_combination in all_combinations(lines[1:]):
                yield [line] + rest_combination

def reduce(combination):
    """
    reduce a combination by returning the number of
    times each value appear consecutively, ie.
    [1,1,4,4,3] would return [2,2,1] since
    the 1's appear twice, the 4's appear twice, and
    the 3 only appear once.
    """

    result = []
    while combination:
        count = 1
        value = combination[0]
        combination = combination[1:]
        while combination and combination[0] == value:
            combination = combination[1:]
            count += 1
        result.append(count)
    return tuple(result)

def calculate_best_choice(lines):
    """
    find the best choice by reducing each available
    combination down to the number of stops you can
    sit on a single line before having to switch,
    and then picking the one that has the most stops
    first, and then so on.
    """

    available = []
    for combination in all_combinations(lines):
        count_stops = reduce(combination)
        available.append((count_stops, combination))
    available = [k for k in reversed(sorted(available))]
    return available[0][1]

possible_lines = calculate_possible_exit_lines(stops)
print("possible lines: %s" % (str(possible_lines), ))
best_choice = calculate_best_choice(possible_lines)
print("best choice: %s" % (str(best_choice), ))

This code prints:

此代码打印:

possible lines: [[1, 4], [2, 4], [2]]
best choice: [4, 4, 2]

Since, as I said, I list lines between stops, and the above solution can either count as lines you have to exit from each stop or lines you have to arrive on into the next stop.

因为,正如我所说的,我列出了停靠点之间的行,并且上述解决方案可以计为您必须从每个停靠点退出的行或您必须到达下一站的行。

So the route is:

所以路线是:

• Hop onto line 4 at stop A and ride on that to stop B, then to stop C

跳到A站的4号线上,然后骑上B站,然后停在C站

• Hop onto line 2 at stop C and ride on that to stop D

跳到C站的2号线上然后骑上去停止D.

There are probably edge-cases here that the above code doesn't work for.

这里可能有边缘情况,上面的代码不起作用。

However, I'm not bothering more with this question. The OP has demonstrated a complete incapability in communicating his question in a clear and concise manner, and I fear that any corrections to the above text and/or code to accommodate the latest comments will only provoke more comments, which leads to yet another version of the question, and so on ad infinitum. The OP has gone to extraordinary lengths to avoid answering direct questions or to explain the problem.

但是,我对这个问题并不感兴趣。 OP已经证明完全无法以清晰简洁的方式传达他的问题,我担心对上述文本和/或代码的任何更正以适应最新的评论只会引发更多的评论,这导致另一个版本的无限的问题,等等。 OP已经不遗余力地避免回答直接问题或解释问题。

#5

I'm going to take a crack here based on the comments, please feel free to comment further to clarify.

我将根据评论在这里采取一个裂缝,请随时进一步澄清澄清。

We have N arrays and we are trying to find the 'most common' value over all arrays when one value is picked from each array. There are several constraints 1) We want the smallest number of distinct values 2) The most common is the maximal grouping of similar letters (changing from above for clarity). Thus, 4 t's and 1 p beats 3 x's 2 y's

我们有N个数组,当从每个数组中选取一个值时,我们试图找到所有数组的“最常见”值。有几个约束1)我们想要最小数量的不同值2)最常见的是相似字母的最大分组(为清楚起见,从上面改变)。因此,4 t和1 p击败3 x 2 y

I don't think either problem can be solved greedily - here's a counterexample [[1,4],[1,2],[1,2],[2],[3,4]] - a greedy algorithm would pick [1,1,1,2,4] (3 distinct numbers) [4,2,2,2,4] (two distinct numbers)

我认为这两个问题都不能贪婪地解决 - 这是一个反例[[1,4],[1,2],[1,2],[2],[3,4]] - 一个贪婪的算法会选择[1,1,1,2,4](3个不同的数字)[4,2,2,2,4](两个不同的数字)

This looks like a bipartite matching problem, but I'm still coming up with the formulation..

这看起来像一个二分匹配问题,但我仍然想出这个配方..

EDIT : ignore; This is a different problem, but if anyone can figure it out, I'd be really interested

编辑:忽略;这是一个不同的问题,但如果有人能搞清楚,我会非常感兴趣

EDIT 2 : For anyone that's interested, the problem that I misinterpreted can be formulated as an instance of the Hitting Set problem, see http://en.wikipedia.org/wiki/Vertex_cover#Hitting_set_and_set_cover. Basically the left hand side of the bipartite graph would be the arrays and the right hand side would be the numbers, edges would be drawn between arrays that contain each number. Unfortunately, this is NP complete, but the greedy solutions described above are essentially the best approximation.

编辑2:对于任何有兴趣的人,我误解的问题可以表述为Hitting Set问题的一个实例,请参阅http://en.wikipedia.org/wiki/Vertex_cover#Hitting_set_and_set_cover。基本上,二分图的左侧是数组,右侧是数字,在包含每个数字的数组之间绘制边。不幸的是,这是NP完全,但上面描述的贪婪解决方案基本上是最好的近似。