Finden Sie die maximale Anzahl von Paaren in einer Liste von Paaren
Ich habe eine Liste von Paaren, die ich aus bestimmten Zahlen generiert habe. Meine Frage bezieht sich nicht darauf, wie meine Paare berechnet werden, wie ich das herausgefunden habe, sondern auf die Maximierung der insgesamt möglichen Anzahl von Paaren.
Beispielsweise:
[1,3,7,19,13,21]
ergibt sich
{1:[19,13,21],
3:[7,19],
7:[3,19,13],
19:[1,3,7,21],
13:[1,7,21],
21:[1,19,13]}
1 kann mit 19, 13 oder 21 gepaart werden. 3 kann mit 7 oder 19 gepaart werden, und so weiter. Mein Ziel ist es, die einzigartige Paarung so zu maximieren, dass ich ohne Paar am wenigsten Punkte übrig habe. In diesem Fall können Sie 1-13, 3-7 und 19-21 haben, was 0 Reste ergibt. Du könntest aber auch 1-19, 7-13 machen, was 3 und 21 ohne Partner übrig lässt.
Gibt es einen Algorithmus, der dieses Problem schon einmal behandelt hat? Ich dachte darüber nach, sie in ein Diagramm einzufügen und zu versuchen, den größten Hamilton-Pfad zu finden, aber das scheint praktisch unmöglich zu sein. Ich mache dies in Python, also habe ich Wörterbücher und Listen, die ich als Container verwendet habe.
Bearbeiten: Die Bedingungen dafür, ob eine Zahl gepaart werden kann, ist, ob sie mit dem Paar ein bestimmtes Muster bilden. Bei zwei Zahlen x und y folgen sie diesem Muster bis x == y oder es dauert ewig. Wenn x < y, y = y - x und x = 2 * x. Dann geht es wieder usw...
Das Problem, das Sie beschreiben, besteht darin, das maximale Matching in einem Graphen zu finden (in Ihrem Beispiel ist if i
mit j
dann j
auch mit gepaart i
, sodass Sie sie durch eine Kante verbinden können). Das folgende Python-Paket sowie dieser Code enthalten relevante Implementierungen.