Suche nach einer guten Übereinstimmung von zwei Listen von Zahlen

Question

Ich habe zwei Sätze von Zahlen, mit SET2 mit mehr Elemente in der Regel. Es ist garantiert, dass die Anzahl von SET2 gleich oder größer als die Anzahl SET1 ist. Da die Reihenfolge wichtig ist, sind die Einträge eher Listen als Sets.

Mein Ziel ist es (zusammenzufassen) zu kombinieren/neu ordnet die Zahlen von SET2, um es so ähnlich machen zu SET1 wie möglich. Ich definiere die Ähnlichkeit als die Summe der Abweichungen an jeder Position. Siehe this post für die Art, wie ich die Ähnlichkeit berechnen. Je kleiner die Summe, desto besser.

Mein erster Ansatz war es, alle Kombinationen auszuprobieren und die beste auszuwählen. Dies funktioniert nur bei sehr kleinen Sets (besonders beim zweiten). Siehe this post und die Antwort von Rawling. Gibt es einen klügeren Weg, um eine gute Kombination zu bekommen? Ich brauche definitiv nicht die beste. Ein guter würde als Ergebnis gut sein. Offensichtlich sind Sätze mit leeren Teilmengen Unsinn. Extrem unausgewogene Sets scheinen mir nicht sehr vielversprechend zu sein. SET1 neigt dazu, ungefähr 8 zu haben, kann aber bis zu 18 Einträge haben. SET2 hat oft eine Anzahl von mehr als 10 (bis zu 35). Die Summe der Zahlen in den beiden Sätzen ist gleich (außer bei Rundungsfehlern). Hier

ist ein Beispiel mit guten und schlechten Ergebnissen (nicht alle möglichen ist):

SET1 = { 272370, 194560, 233430 }; SET2 = { 53407.13, 100000, 365634.03, 181319.07 } 

     272370   |  194560   |  233430 
--------------------------------------------------------------------- 
    365634.03   | 100000 + 53407.13 |  181319.07  (best match) 
    365634.03   |  181319.07  | 100000 + 53407.13 (good) 
    365634.03   |  100000   |181319.07 + 53407.13 (ok) 
     53407.13   |365634.03 + 100000 |  181319.07  (bad) 
     53407.13   |365634.03 + 181319.07 |  100000  (bad) 
.     |365634.03 + 181319.07 | 53407.13 + 100000 (invalid) 
53407.13 + 100000 |365634.03 + 181319.07 |      (invalid) 

Bitte lassen Sie mich wissen, wenn ich eine Prämisse zu beschreiben vergessen oder meine Beschreibung ist unklar oder sogar fehlerhaft. Ich bin auch glücklich, ein anderes Beispiel zu geben.

Vielen Dank im Voraus!

Answer 1

Heuristik, die recht gut funktionieren sollte:

1. list<int> set1, set2; 
2. sort(set2) // decreasing, set2[0] would be the greatest value in set2 
3. struct set1item = {set1index, value, list<int> chosen} 
4. prepare list<set1item> set1items from set1 //(index = index in set1 list, value = set1[index] and chosen = null) 
5. put set1items to some priorityqueue pq // ordered by value 
6. for each set2item in set2{ 
7.  item = pq.first() 
8.  item.chosen.add(set2item); 
9.  item.value -= set2item; 
10. pq.updateFirst(item) 
11.} 

Es ist wie funktionieren würde: iterieren set2 von der höchsten zur niedrigsten zu, von set1 tatsächlichen höchste Element erhalten, verringern sie durch das Element von set2 bekam und dieses Element hinzufügen von set2 zu element von set1 results.

Sie müssen daran denken, zu überprüfen, ob alle Elemente von set1 kein leeres Ergebnis haben.

Beispiel1: Set1 = {20, 9, 7, 3}, Set2 = {7, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2}.

iter1: fromSet2 = 7, Set1 = {20:{}, 9:{}, 7:{}, 3:{}}, fromSet1=20. Verringerung von 20 um 7 und Hinzufügen von 7 zu seinem Ergebnis. Aktualisiert: Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}.

iter2: fromSet2 = 6, Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}, . Absteigend 13 von 6 und Hinzufügen von 6 zu seinem Ergebnis. Aktualisiert: Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}.

iter3: fromSet2 = 6, Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}, fromSet1=9. Absteigend 9 von 6 und Hinzufügen von 6 zu seinem Ergebnis. Aktualisiert: Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}.

iter4: fromSet2 = 4, Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}, fromSet1=7. Abnahme von 7 um 4 und Hinzufügen von 4 zu seinem Ergebnis. Aktualisiert: Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}.

iter5: fromSet2 = 2, Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}, fromSet1=7. Verringerung von 7 um 2 und Hinzufügen von 2 zu seinem Ergebnis. Aktualisiert: Set1 = {3:{7, 6, 4}, 3:{6}, 5:{2}, 3:{}}.

...