두 개의 인덱스 목록을 결합하여 두 개의 다른 목록간에 1-1 매핑을 만듭니다.

Question

예제부터 시작하겠습니다.

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

이들 두 목록 아래 표에 나타낸 바와 같이 A가 (순서) 다른리스트 내의 요소들을 선호 가지고

나는 두 개의리스트가있다. 세그먼트는 특정 레이블을 가져야한다고 생각할 수 있지만 해당 레이블은 해당 세그먼트를 가져야한다고 생각하지 않습니다.

 | 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에 매핑"을 만들려면 어떻게해야합니까? 즉 세그먼트는 테이블에서 가능한 한 왼쪽으로 레이블을 가져오고 그 반대도 마찬가지입니다. 세그먼트와 레이블이 선호 목록에없는 경우에도 알고리즘은 쌍을 강제해야합니다 (단, 가능한 한 피해야합니다).

나는 위의 예제에 대한 최선의 대답을 알지 못합니다. 일부 대답은

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

일 수 있습니다. 그러나 일치하는 라벨이없는 세그먼트는 어떻게 선택합니까? 그리고 어느 것이 가장 최적인지 어떻게 계산합니까?

거의 모든 것이 다를 수 있습니다. 세그먼트와 레이블의 길이가 동일 할 필요는 없으며 인덱스 목록은 동일한 길이 일 필요가 없습니다. 알고리즘 속도는 항상 중요하지만이 경우에는 세그먼트 또는 레이블에서 10-20 개 이상의 요소로 작업하지 않을 것이라고 말할 수 있습니다.

내 문제는이 문제를 해결하는 방법에 대한 진입 점이 없다는 것입니다. 대부분이 문제를 해결하는 알고리즘이 있지만 그 이름을 모른다. 이 문제는 문제가 해결 안정된 결혼 문제

알고리즘의 아이디어라고

Answer 1

) 또한 경우에 당신은 콘크리트가 아닌 의사 코드 예제를 만들고 싶어, 자바에서 이것을 구현하고 있습니다 각 세그먼트는 환경 설정 목록에서 선호하는 세그먼트에 아직 할당되지 않은 다음 라벨에 연속적으로 할당됩니다.

이것은 최적의 일치를 향해 수렴합니다 (두 개 이상있을 수 있음). 여기

(나는 당신의 자신의 위험에 사용, 그 정도를 테스트하지 않았다) 자바 예입니다)

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 루프에

주 후 작은 기능은 흥미 없습니다 :)

당신이 더 많은 정보를 정기적으로 찾을 수 있습니다

: https://en.wikipedia.org/wiki/Stable_marriage_problem

,691,363을210

환호