Gruppierung von Strings

Question

Ich habe eine Liste von möglichen Gruppen für eine Liste von Strings. Jede Zeichenfolge besteht aus mehreren Wörtern, die die Zeichenfolgenelemente sind. Ich möchte die Strings nach diesen Elementen gruppieren.

Jede Gruppe basiert auf einem gemeinsamen Wort: Alle Strings in der Gruppe müssen dieses Wort enthalten - obwohl ich nicht verlangen muss, dass alle Strings, die dieses Wort enthalten, in derselben Gruppe sind. Eine Zeichenkette mit N Worten kann in einem beliebigen N verschiedenen Gruppen stehen. Jeder String darf nur in einer Gruppe sein. Jede Gruppe muss mindestens zwei Strings haben.

Ziel: Bilden Sie die Gruppen, um die Anzahl der Zeichenfolgen zu maximieren, die sich in einer Gruppe befinden (minimieren Sie "verwaiste" Zeichenfolgen).

Zum Beispiel, wenn ich die folgende Liste von Zeichenketten haben:

cycle cost 
pump cost 
cycle analysis 
cost example 

Ich hätte alle möglichen Wörter jedes Strings als potentielle Gruppen. Ich möchte nun diese Zeichenfolgen so gruppieren, dass alle oder so viele wie möglich in eine Gruppe gelangen.

Ich habe den naiven Ansatz versucht, die Gruppe mit den meisten Strings zuerst zu nehmen, was in diesem Beispiel cost wäre, aber dies lässt cycle analysis ohne eine Gruppe.

Das Ergebnis bin ich in diesem Beispiel suchen ist:

cycle: cycle cost, cycle analysis 
cost: pump cost, cost example 

Gibt es dort einen Algorithmus für diese Art von Problem schon? Hinweise zur Vorgehensweise wären hilfreich.

Answer 1

Es sieht aus wie @ m69 hat eine gute Führung. Ihr Problem hat ein paar Modifikationen:

• Entfernen Sie alle Sätze der Größe 1;
• Wenn ein Satz ist (vorläufig) zu der Lösung, die alle Elemente dieses Satzes muss von allen übrigen Sätzen
  • ... und alle Sätze mit weniger als zwei Elementen entfernt bekommen entfernt werden.

Leider ist das NP-schwer, bei besten. Wenn die Eingabe der Anwendung nicht lächerlich groß ist, würde ich eine Brute-Force-Heuristik mit liberalem Backtracking verwenden.

Initialisierung:

• A tragfähige Satz ist einer mit mindestens 2 Elementen.
• Bearbeiten Sie Ihre Liste.
  • Legen Sie alle tragfähige Sätze in eine Liste S.
  • Platzieren Sie alle Elemente in das Universum, U.

Prozess:

1. Pick a set P von S; füge es zur Lösungsliste hinzu.
2. entfernen alle Elemente P von jedem in S gesetzt bleibt.
3. Entfernen Sie alle nicht lebensfähigen Sätze von S.
4. Wenn S leer
   • Dann Wenn alle Elemente von U existieren in S,
     • Dann und Bericht-Lösung stoppen.
     • Else Rückkehr zur vorherigen Aufrufebene
   • Else [S nicht leer] auf diesen Prozess Wiederholt mit dem neuen S
5. Wenn Rekursion Erfolg berichtet,
   • Dann zurück zum vorherigen Aufruf lev el.
   • Else gehen zurück zu Schritt 1, und wählen Sie den nächsten Satz von S

Sie können in S durch eine vernünftige Ordnung der Sätze in diesem einige Vorteile gewinnen. Ich empfehle einen Greedy-Algorithmus mit einem Wert gemessen nach der wünschenswert seines Elements in den Sets S. Zum Beispiel würde ein Element, das in nur eine Menge erscheint, diese an den Anfang der Liste schieben.

Geht das los?