java - 合并两个索引列表以在其他两个列表之间创建 1-1 映射

Question

我们将从示例开始。

我有两个列表:

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

这两个列表优先(按顺序)另一个列表中的一些元素，如下表所示。请注意，一个片段可以认为它应该有某个标签，而相应的标签认为它不应该有那个片段。

       | 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

可以用两个索引列表的形式表示:

// 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]]

现在，如何在段和标签之间创建“最佳的一对一映射”？即，段在其表中尽可能多地获得标签，反之亦然。该算法应该强制配对，即使段和标签在它们的偏好列表中没有彼此(但是，应该尽可能避免这种情况)。

我不知道上面例子的最佳答案是什么。一些答案可能是

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

但是如果没有匹配的标签，我该如何选择分割呢？我如何计算哪一个是最佳的？

如您所见，几乎所有内容都可以变化。段和标签不必等长，索引列表也不必等长。虽然算法速度始终很重要，但我可以说，在这种情况下，我不会在段或标签中处理超过 10-20 个元素。

我的问题是我不知道如何解决这个问题。很可能有一种算法可以解决这个问题，但我不知道它的名字。我也在 Java 中实现了这个，以防你想制作一个具体的非伪代码示例；)

Answer 1

这个问题叫做稳定婚姻问题

解决此类问题的算法的想法是，您的每个片段将依次分配给其偏好列表中尚未分配给它偏好的片段的下一个标签。

这将收敛到一个最佳匹配(请注意，可以有多个)。

这是一个 java 示例(我没有对其进行太多测试，使用风险自负；))

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;
  }
}

您可以使用更面向对象的方法做得更好，但这只是一个开始:)

本质部分在while循环中，main后面的小函数没什么意思:)

您可以在那里找到更多信息:https://en.wikipedia.org/wiki/Stable_marriage_problem

干杯