Combine two lists of indices to create a 1-1 mapping between two other lists

Question

We'll start with the example.

I have two lists:

segments = [16, 19, 22, 26]
labels = [horse, cow, mule]

These two lists has a prefers (in order) some of the elements in the other list as shown in the tables below. Note that a segment can think that it should have a certain label, while the corresponding label doesn't think it should have that segment.

       | Preferred Label                 | Preferred Segment
       | (in order, L -> R)              | (in order, L -> R)
    ---+-------------------        ------+-------------------
    16 | horse, cow, mule          horse | 26, 19, 22, 16
    19 | horse, mule               cow   | 16, 22, 19
    22 | mule, cow, horse          mule  | 26, 22, 19
    26 | mule

which can be expressed in the form of two index lists:

// We have 4 segments, each have a ranked list (length 0-3) of preferred label
labelIndicesForSegments = [[0, 1, 2], [0, 2], [2, 1, 0], [2]] 

// We have 3 labels, each have a ranked list (length 0-4) of preferred segment
segmentIndicesForLabels = [[3, 1, 2, 0], [0, 2, 1], [3, 2, 1]]

Now, how do I create the "optimal 1 to 1 mapping" between segments and labels? I.e., the segments gets a label as much to the left as possible in its table, and vice versa. The algorithm should force pairs even if a segment and a label doesn't have each other in their preference list (this, however, should be avoided as far as possible).

I do not know what would be the best answer to the example above. Some answers could be

1: [(16, horse), (19, mule), (22, cow)]
2: [(16, cow), (19, horse), (26, mule)]
3: [(19, horse), (22, cow), (26, mule)]

But how do I choose what segment will be without a matching label? And how do I compute which one is the most optimal?

As you can see pretty much everything can vary. Segments and labels doesn't have to be of equal length and the list of indices doesn't have to be of equal length. While algorithm speed always matters I can say that in this case I won't be working with more than 10-20 elements in either segments or labels.

My problem is that I have no entry point on how to solve this. Most likely there is an algorithm to solve this but I don't know it's name. I'm also implementing this in Java, in case you want to make a concrete non-pseudocode example ;)

Answer 1

This problem is called the stable marriage problem

The idea of the algorithm to solve such a problem is that each of your segments will successively be assigned to the next label on its preference list that is not already assigned to a segment it prefers.

This will converge towards an optimal matching (note that there can be more than one).

Here is a java example (I didn't test it that much, use at your own risk ;) )

class SMP {
  static int[] segments = {16, 19, 22, 26};
  static String[] labels = {"horse", "cow", "mule"};

  static int[][] labelIndicesForSegments = {{0, 1, 2}, {0, 2}, {2, 1, 0}, {2}};
  static int[][] segmentIndicesForLabels = {{3, 1, 2, 0}, {0, 2, 1}, {3, 2, 1}};

  static int[] matching = new int[segments.length];
  static int[] nextLabel = new int[segments.length]; // A simple pointer to the next label to test for each segment (the current position in its own preference list) 

  public static void main(String[] args) {
    // initialize all matchings
    for (int i=0; i<matching.length; i++) {  
      matching[i] = -1;
      nextLabel[i] = 0;
    }

    // While there is at least one free label and one free segment  
    while (canEnhance()) {
      int unmatched = findUnmatchedSegment(); // Pick an unmatched segment
      int label = labelIndicesForSegments[unmatched][nextLabel[unmatched]];

      nextLabel[unmatched]++;

      int matchedSegment = getMatchedSegment(label);

      if (matchedSegment == -1) { // The label is not matched
        matching[unmatched] = label;
      } else {
        if (labelPrefersSegment(label, matchedSegment, unmatched)) {
          matching[unmatched] = label;
          matching[matchedSegment] = -1;
        }
      }
      for (int i = 0; i < matching.length; i++) {
                if (matching[i] != -1)
                  System.out.println("Segment "+segments[i]+" matched with label "+labels[matching[i]]);
              }
      System.out.println("-----");
    }

    for (int i = 0; i < matching.length; i++) {
      if (matching[i] != -1)
        System.out.println("Segment "+segments[i]+" matched with label "+labels[matching[i]]);
    }
  }

  public static boolean labelPrefersSegment(int label, int currentSegment, int newSegment) {
    int[] preferenceList = segmentIndicesForLabels[label];

    for (int i = 0; i < preferenceList.length; i++) {
      if (preferenceList[i] == currentSegment) return false;
      if (preferenceList[i] == newSegment) return true;
    }
    return false;
  }

  public static int getMatchedSegment(int label) {
    for (int i=0; i<matching.length; i++) {
      if (matching[i] == label) return i;
    }
    return -1;
  }

  public static int findUnmatchedSegment() {
    for (int i=0; i<matching.length; i++) {
      // The segment need to be free and to still have labels to test
      if (matching[i] == -1 && nextLabel[i] < labelIndicesForSegments[i].length) {
        return i;
      }
    }
    return -1;
  }

  public static boolean canEnhance() {
    return findUnmatchedSegment() != -1;
  }
}

You could do better using a more object-oriented approach but that's a start :)

The essential part is in the while loop, the small functions after the main are not that interesting :)

You can find more infos there : https://en.wikipedia.org/wiki/Stable_marriage_problem

Cheers