Subsequenzen mit der höchsten Anzahl an Übereinstimmungen?

Question

Bei einem 2D-Array von Daten, wie finde ich die größte Kombination mit den meisten Übereinstimmungen?

Beispiel:

Kd. Nr.  Prod Nr.
C1      P1
C1      P2
C2      P1
C2      P3
C3      P1
C3      P3
C3      P4

(Verwendung von Haskell - konnte nicht herausfinden, wie dies einfach in C# gemacht werden kann, was gewünscht wird) Die Teilfolgen sind:

    > subsequenc­es \["P1"­,"P2","P3"­, "P4"\]­
    => \[\[\],\["P1"\],\["P2"\],\["P1","P2"\],\["P3"\],\["P1","P3"\],\["P2","P3"\],\["P1","P2","P3"\],\["P4"\],\["P1","P4"\],\["P2","P4"\],\["P1","P2","P4"\],\["P3","P4"\],\["P1","P3","P4"\],\["P2","P3","P4"\],\["P1","P2","P3","P4"\]\]

Ich möchte eine Teilfolge der Größe X mit mehr als Y Übereinstimmungen finden...

Also, für dieses Beispiel ist die größte Teilfolge mit mehr als einer Übereinstimmung: ["P1", "P3"] - mit 2 Übereinstimmungen

Da die individuellen Kundensequenzen sind:

    C1 => \["P1", "P2"\]
    C2 => \["P1", "P3"\]
    C3 => \["P1", "P3", "P4"\]

Also gibt es zwei Instanzen von ["P1", "P3"] in diesen Sätzen.

Mein erster Gedanke war es, die Teilfolgen zu generieren und dann abzugleichen, aber mein Datensatz ist zu groß.

Hinweis: Mein Datensatz enthält 13000 eindeutige Kombinationen von 2D-Daten, daher ist der Teilfolgenansatz entweder überlaufen oder hat nie geendet, abhängig von der Sprache.

EDIT: Ich bin an der längsten Teilmenge interessiert (nicht geordnet)

EDIT: @Jimmy: Wenn Sie Folgendes zu Ihrer Liste hinzufügen, hätte ich erwartet, dass P1, P2, P4 das Ergebnis sind, da es die meisten Kunden mit diesem Korb hat. Ihre Lösung funktioniert leider nicht

    { "C4", new HashSet(new[] { "P1", "P2","P4"})},
    { "C5", new HashSet(new[] { "P1", "P2","P4"})},
    { "C6", new HashSet(new[] { "P1", "P2","P4"})},

EDIT: @Eric Lippert

Meine ideale Ausgabe wäre jede Kombination und jedes Mal, wenn es eine Teilmenge war. Dann könnte ich eine Abfrage der größten Körbe mit einer Mindestanzahl von Waren in diesem Korb machen.

EDIT: Um es aus einer geschäftlichen Perspektive zu sehen, möchte ich den am häufigsten vorkommenden Warenkorb finden, den viele meiner Kunden kaufen. Mir ist bewusst, dass viele und die Größe des Korbs vage sind - aber hier kommt die Analyse des Ergebnisses ins Spiel.

Answer 1

Dieses Problem kann wie folgt formuliert werden (sofern ich dich richtig verstehe):

Gegeben sind n Mengen: C1 ... CN, jede zusammengesetzt aus den Elementen {P1 ... PN}

Finde eine Schnittmenge X dieser Teilmengen mit mindestens Y Elementen.

Das komplexere Problem, die maximale Schnittmenge dieser N Mengen zu finden, ist NP-Schwer (vgl. diesen Beweis).

Dein Problem könnte ebenfalls NP-schwer oder NP-vollständig sein (da es wie die Entscheidungsversion des Problems der maximalen Schnittmenge aussieht). Du wirst keine effiziente Lösung für dein Problem finden.

Du solltest nach Heuristiken für das Problem der maximalen Schnittmenge suchen oder dich inspirieren lassen, indem du dir ähnliche (aber unterschiedliche) und bekanntere Probleme wie das Mengenabdeckungsproblem anschaust.

Answer 2

Was du hast, ist ähnlich wie das hier 1 a | 1 b | 1 c

2 a | 2 b

3 c | 3 d

Was äquivalent ist zu

abc | ab | cd

Also ist das Problem, das du zu lösen versuchst, entweder 1. Finde den längsten String 2. Finde den String mit der höchsten Häufigkeit 3. Kombination davon

Stelle die Serie als Vektor dar, schreibe eine benutzerdefinierte Vergleichsfunktion für diesen Vektor, füge sie zu einem Multiset hinzu, während du die Anzahl behältst. UND denke daran, den bisher größten Zähler für die häufigste Sequenz und den längsten eingefügten Vektor zu behalten.

Answer 3

Nur die längste Teilfolge beantworten:

Kunde c = entryList[0].Kunde;
Produkt p;
set s;
set largestSet = s;
für (jeden Eintrag in entryList)
{
  if(c ! = Eintrag.Kunde)
   {  
     c = Eintrag.Kunde;
     if (s.size > largestSet.size)    largestSet = s;
     s.clear();
   }

   s.add(Eintrag.Kunde)
}

Answer 4

Es scheint, dass Sie nach der längsten Paar-Teilmenge suchen.

So geht es auf die harte Tour:

Ausgehend von einer Liste von Tupeln (c,p) erstellen Sie ein Wörterbuch mit {c:set(p1,p2,p3)}.

var dict = new Dictionary> {
    { "C1", new HashSet(new[] { "P1", "P2"})},
    { "C2", new HashSet(new[] { "P1", "P3"})},
    { "C3", new HashSet(new[] { "P1", "P3","P4"})},
};
var max = from pair1 in dict
          from pair2 in dict
          where pair2.Key != pair1.Key
          let s = pair1.Value.Intersect(pair2.Value).ToArray()
          orderby s.Length descending
          select s;

Console.WriteLine(string.Join(",", max.First()));

---

Ausgabe:

P1,P3

Scheint ein O(N^3) Algorithmus zu sein.