Algorithm to find "most common elements" in different arrays

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

1. Starting at i = 0
2. current = arrays[i]
3. Loop i from i+1 to len(arrays)-1
4. new = current & arrays[i] (set intersection, finds common elements)
5. If there are any elements in new, do step 6, otherwise skip to 7
6. current = new, return to step 3 (continue loop)
7. print or yield an element from current, current = arrays[i], return to step 3 (continue loop)

Here is a Python implementation:

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

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.
3. Restart step 2 from the next element

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.

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:

             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.

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

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
• Hop onto line 2 at stop C and ride on that to stop 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.

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

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)

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.