Erkennen von Zahlenpaaren

[lowmax_5]

Folgende Problematik stellt sich:

Eingabe:

1. Geben sind zwei Mengen von Zahlenpaaren
   
2. Die Summe der Menge 1 ist gleich der Summe von Menge2
   
3. Es sollen nun Kombinationen zusammengestellt werden
   
4. Menge1: (2,6,7,1,6,15,7,4,1) ==> Summe 49
   
5. Menge2 (16,13,9,11) ==> Summe 49

Ausgabe:

1. Welche Zahlen ergeben welche Summen? z.b. (16==>15+1) + (13==>7+6) + (9=>2+6+1) + (11=>7+4)
   
2. Ist Ergebis eindeutig oder gibt es mehrere Kombinationsmöglichkeiten?
   
3. Gesucht ist die Lösung mit den besten Kombinationen (Möglichst kurz)

Wie kann ein Lösungansatz aussehen? Bin für jeden Tipp dankbar!

[Zacherl]

Falls es da nicht irgendeine ausgefeilte mathematische Herangehensweise gibt, die mir unbekannt ist, würde ich auf Bruteforce (Erzeugen sämtlicher Permutationen) zurückgreifen. Soll es möglichst performant sein, kannst du auch Backtracking verwenden.

[lowmax_5]

Zitat:

...Soll es möglichst performant sein...

... Alles was unter einer Sekunde ist, ist akzeptabel!

[JasonDX]

Zitat:

Zitat von lowmax_5 (Beitrag 1318058)

Zitat:

...Soll es möglichst performant sein...

... Alles was unter einer Sekunde ist, ist akzeptabel!

Für welche Eingabegröße? 10 Zahlen, 100, 1000, 1000000?

Wenn ich mich nicht ganz täusche, ist das Problem NP-vollständig, d.h. eine "einfache, schnelle" Lösung gibts nicht. Brute-Force ist die wahrscheinlich einfachste Variante, die für kleine Mengen auch kein Problem darstellen sollte.

[lowmax_5]

Zitat:

Für welche Eingabegröße? 10 Zahlen, 100, 1000, 1000000?

Bis 1000 reicht in diesem Fall aus.

[BUG]

Mhm, auf den ersten Blick sah es nach Partition aus, allerdings scheinst du ja eine passende Partition zu haben.
EDIT: JasonDX hat recht; das Partitionsproblem sollte sich darauf reduzieren lassen. Eingabe von Partition wird M1, M2 hat zwei Elemente: jeweils die Hälfte der Summe aller Elemente in M1.

Ich verstehe das Problem so: finde für jedes Element aus Menge2 eine Summe aus Elementen aus Menge1, sodass kein Element aus Menge1 doppelt verwendet wird (?)

Klar ist, dass dann immer alle Elemente von Menge1 benutzt werden müssen, da die Summe der Elemente gleich ist. Was heißt also ein "kurzes Ergebnis"?

Es gibt nicht immer ein Ergebnis. Beispiel:
M1 = 2, 4, 6
M2 = 3, 9

Es kann unterschiedliche Ergebnisse geben (welches ist hier besser/kürzer?):
M1 = 1, 2, 2, 3
M2 = 5, 3
5 = 1 + 2 + 2 und 3 = 3
5 = 2 + 3 und 3 = 2 + 1

[Dejan Vu]

Korrigiert mich bitte, aber wenn es hier um Teilmengen (nicht Partitionen) geht, dann ist das doch popelig. ;-)

Also: Gegeben zwei Mengen A und B. Gesucht ist die Menge aller Teilmengen T, sodass für jedes t aus T gilt: Es existiert ein Element b aus B mit b=Summe der Elemente aus t.

Beispiel: A = (1,2,3,4). B=(5,7,10)
Teilmengen =
(1),(2),(3),(4),
(1,2),(1,3),(1,4),
(2,3),(2,4),(3,4),
(1,2,3),(1,2,4),(2,3,4),
(1,2,3,4)
Die Teilmengen 't', deren Summe entweder 5,7 oder 10 ist, sind fett markiert.

Ich muss also nur alle Teilmengen aus A bilden, summieren und schauen, ob der Wert in B vorkommt. Ganz einfach. Dauert nur. Denn es gibt 2^n Teilmengen einer n-elementigen Menge.

[BUG]

Zitat:

Zitat von Dejan Vu (Beitrag 1318108)

Ganz einfach. Dauert nur. Denn es gibt 2^n Teilmengen einer n-elementigen Menge.

Und dir ist klar das 2^1000 eine nicht unbedingt kleine Zahl ist? Also ich könnte verstehen, das man sein Ergebnis haben möchte bevor das Universum den Wärmetod stirb ... vielleicht hat man ja Glück und hat nur einfache Instanzen, für die es im Regelfall schneller geht.

Ich wäre schon neugierig, was das für ein echtes Problem ist, das lowmax da lösen möchte :stupid:

[ibp]

Zitat:

Zitat von Dejan Vu (Beitrag 1318108)

Korrigiert mich bitte, aber wenn es hier um Teilmengen (nicht Partitionen) geht, dann ist das doch popelig. ;-)

Also: Gegeben zwei Mengen A und B. Gesucht ist die Menge aller Teilmengen T, sodass für jedes t aus T gilt: Es existiert ein Element b aus B mit b=Summe der Elemente aus t.

Beispiel: A = (1,2,3,4). B=(5,7,10)
Teilmengen =
(1),(2),(3),(4),
(1,2),(1,3),(1,4),
(2,3),(2,4),(3,4),
(1,2,3),(1,2,4),(2,3,4),
(1,2,3,4)
Die Teilmengen 't', deren Summe entweder 5,7 oder 10 ist, sind fett markiert.

Ich muss also nur alle Teilmengen aus A bilden, summieren und schauen, ob der Wert in B vorkommt. Ganz einfach. Dauert nur. Denn es gibt 2^n Teilmengen einer n-elementigen Menge.

Wenn Sort(A) dann kann man ggf. mit Min(B), Max(B) das ganze noch einschränken und optimieren, besser für kleine Max(B)-Min(B).

[lowmax_5]

Zitat:

Ich verstehe das Problem so: finde für jedes Element aus Menge2 eine Summe aus Elementen aus Menge1, sodass kein Element aus Menge1 doppelt verwendet wird (?)

Ja, das ist korrekt. In Menge B sollen der Einfachheit halber auch alle Elemente verwendet werden. Nach dem Studium Eurerer Beiträge scheint sich eine Lösung für mich wie folgt darzustellen:

1. Bilde Summen Menge1 und und Menge2 ==> Wenn gleich, mache weiter
2. Nun alle Permutationen aus Menge1 erzeugen und Summen bilden
3. Ist die Summe der Permutation in Menge2 enthalten => Wenn Ja=gültig, wenn Nein dann löschen
4. Nun alle Kombinationen bilden, die auf die Gesamtsumme kommen. ==> Diese Kombinationen markieren
5. Sortieren nach den einfachsten Kombinationen ( Am wenigsten summierende Elemente)
Fertig!

Kann das funktionieren? Was meint Ihr dazu?

[Namenloser]

Zitat:

Zitat von BUG (Beitrag 1318101)

Mhm, auf den ersten Blick sah es nach Partition aus, allerdings scheinst du ja eine passende Partition zu haben.

Ich hätte es eher als Rucksackproblem identifiziert, wobei es ja letztlich auf dasselbe herausläuft: Beide sind NP-vollständig.

Mein Lösungsansatz ist ausgehend von dieser Idee: Mal angenommen, es gäbe nur Kombinationen der Länge 2. Dann wäre es ja einfach: Man subtrahiert einfach alle Zahlen aus Menge1 von allen Zahlen aus Menge2. Dann muss man nur noch prüfen, welche dieser Differenzen auch tatsächlich in Menge1 liegen. Schon hat man alle gültigen Paare.

Wenn man mehr als zwei Elemente pro Kombination zulässt, muss man den Ansatz etwas verallgemeinern: Man muss nun für jede Differenz schauen, ob sie wiederum durch eine Kombination von Elementen aus Menge1 gebildet werden kann. Das kann man wieder mit dem gleichen Algorithmus machen. So macht man es iterativ immer weiter, bis man am Ende Summen hat, die man mit einem einzelnen Element erfüllen kann. Der Trick ist, sich für jede Zwischensumme immer die kürzeste, bereits gefundene Kombination zu merken (Prinzip der Dynamischen Programmierung). Da die Kombinationen immer nur länger werden können, ist die erste gefundene Kombination automatisch immer auch die kürzeste.

Ich habe das mal als Proof-of-Concept implementiert. TCombinationTable sollte man in einer richtigen Implementierung als Hashtable implementieren, dazu war ich jetzt aber zu faul.

Das Programm gibt allerdings immer nur die kürzeste Kombination aus, nicht, ob es noch weitere Kombinationen gibt. Das wäre IMO nur noch mit Brute-Force zu machen.

Beispiel Ein- und Ausgabe:

Delphi-Quellcode:

PARTS: array [0..8] of Integer = (2,6,7,1,6,15,7,4,1);
SUMS: array [0..3] of Integer = (16,13,9,11);

Code:

16 = 15 + 1
13 = 7 + 6
9 = 7 + 2
11 = 7 + 4

Delphi-Quellcode:

PARTS: array [0..16] of Integer = (2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1);
SUMS: array [0..6] of Integer = (1,2,3,16,13,9,11);

Code:

2 = 2
1 = 1
3 = 2 + 1
9 = 2 + 1 + 2 + 1 + 2 + 1
11 = 1 + 1 + 2 + 1 + 2 + 1 + 2 + 1
13 = 1 + 1 + 1 + 1 + 2 + 1 + 2 + 1 + 2 + 1
16 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 2 + 1 + 2 + 1

Scheint zu funktionieren.

Edit: Habe noch ein paar Fehler in meinem Code korrigiert, wegen denen die Laufzeit deutlich schlechter war als nötig.

[JasonDX]

Zitat:

Zitat von lowmax_5 (Beitrag 1318162)

1. Bilde Summen Menge1 und und Menge2 ==> Wenn gleich, mache weiter
2. Nun alle Permutationen aus Menge1 erzeugen und Summen bilden
3. Ist die Summe der Permutation in Menge2 enthalten => Wenn Ja=gültig, wenn Nein dann löschen
4. Nun alle Kombinationen bilden, die auf die Gesamtsumme kommen. ==> Diese Kombinationen markieren
5. Sortieren nach den einfachsten Kombinationen ( Am wenigsten summierende Elemente)
Fertig!

Kann das funktionieren? Was meint Ihr dazu?

Du wirst bei 2. scheintern. Nicht bei der Implementierung, sondern bei der Laufzeit.

Bau die Lösung schrittweise auf, und wirf nicht funktionierende Lösungen so schnell wie möglich weg.

[Neutral General]

Mh habe mal schnell was zusammengetippt (Ist in keinster Weise perfekt, aber funktioniert schnell und ohne Probleme).
Es geht in erster Linie ums Prinzip.

Ist jetzt allerdings in C#:

Code:

class Program
{
   private static int GetMaxFittingValueIndex(List<int> list, int DestValue)
   {
      int currIdx = 0;
      for (int i=list.Count-1; i >= 0; i--)
      {
         if (DestValue - list[i] == 0)
            return i;
         else
         if ((DestValue - list[i] > 0) && (list[i] > list[currIdx]))
            currIdx = i;
      }

      return currIdx;
   }

   static void Main(string[] args)
   {
      List<int> MengeA = new List<int>(new int[] { 2, 6, 7, 1, 6, 15, 7, 4, 1 });
      List<int> MengeB = new List<int>(new int[] { 16, 13, 9, 11 });
      Dictionary<int, List<int>> SummenMengeC = new Dictionary<int, List<int>>();

      Console.Write("MengeA: ");
      for (int i = 0; i < MengeA.Count; i++)
         Console.Write(MengeA[i].ToString()+",");
      Console.WriteLine();

      Console.Write("MengeB: ");
      for (int i = 0; i < MengeB.Count; i++)
         Console.Write(MengeB[i].ToString()+",");
      Console.WriteLine();

      MengeA.Sort();
      for (int i=0; i < MengeB.Count; i++)
      {
         List<int> currSummeList = new List<int>();
         int currSumme = 0;
         while (currSumme < MengeB[i])
         {
            int idx = GetMaxFittingValueIndex(MengeA, MengeB[i] - currSumme);
            currSumme += MengeA[idx];
            currSummeList.Add(MengeA[idx]);
            MengeA.RemoveAt(idx);
         }

         SummenMengeC.Add(MengeB[i], currSummeList);
      }

      Console.WriteLine();
      Console.WriteLine("Ergebnis:");

      foreach(int zahl in SummenMengeC.Keys)
      {
         Console.Write(zahl.ToString() + " = ");
         for (int i=0; i < SummenMengeC[zahl].Count; i++)
         {
            if (i < SummenMengeC[zahl].Count - 1)
               Console.Write(SummenMengeC[zahl][i].ToString() + "+");
            else
               Console.Write(SummenMengeC[zahl][i].ToString());
         }
         Console.WriteLine();
      }

      Console.ReadLine();
   }
}

Habe ich was nicht beachtet? Bin mir nicht sicher ob das immer die beste Lösung erzeugt, könnte es mir aber vorstellen.
Irgendwelche Gedanken dazu?

[Namenloser]

Weiß nicht, ob ich deinen Code richtig verstehe, aber ich glaube, der findet nicht immer eine Lösung:

Probier mal

Code:

List<int> MengeA = new List<int>(new int[] { 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int[] { 16 });

Ist aber eine gängige, schnelle Näherungslösung für das Rucksackproblem, soweit ich weiß.

[Neutral General]

Zitat:

Zitat von Namenloser (Beitrag 1318177)

Weiß nicht, ob ich deinen Code richtig verstehe, aber ich glaube, der findet nicht immer eine Lösung:

Probier mal

Code:

List<int> MengeA = new List<int>(new int[] { 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int[] { 16 });

Ist aber eine gängige, schnelle Näherungslösung für das Rucksackproblem, soweit ich weiß.

Vorgabe ist dass die Summe beider Mengen gleich ist. Das ist bei deinem Beispiel nicht der Fall.

Ich nehme mir nacheinander jede Zahl aus der 2. Menge und suche aus der ersten Menge die größten Zahlen mit denen ich die Summe bilden kann.

16:
Größte Zahl <= 16 ist die 15 => 15 zur Summe hinzufügen und aus Menge1 entfernen, 1 ist übrig
Größte Zahl <= 1 ist die 1 => 1 zur Summe hinzufügen und aus Menge1 entfernen, 0 ist übrig => fertig

13:
Größte Zahl <= 13 ist die 7 => 7 zur Summe hinzufügen und aus Menge1 entfernen, 6 ist übrig
Größte Zahl <= 6 ist die 6 => 6 zur Summe hinzufügen und aus Menge1 entfernen, 0 ist übrig => fertig

usw.

[Namenloser]

Zitat:

Zitat von Neutral General (Beitrag 1318178)

Vorgabe ist dass die Summe beider Mengen gleich ist. Das ist bei deinem Beispiel nicht der Fall.

Hmm, aber ändert das was?

Code:

List<int> MengeA = new List<int>(new int[] { 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int[] { 16, 5, 5, 5});

Hier sind die Summen gleich, die Lösung für die 16 wird meines Erachtens aber trotzdem nicht gefunden.

[Neutral General]

Zitat:

Zitat von Namenloser (Beitrag 1318181)

Zitat:

Zitat von Neutral General (Beitrag 1318178)

Vorgabe ist dass die Summe beider Mengen gleich ist. Das ist bei deinem Beispiel nicht der Fall.

Hmm, aber ändert das was?

Code:

List<int> MengeA = new List<int>(new int[] { 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int[] { 16, 5, 5, 5});

Hier sind die Summen gleich, die Lösung für die 16 wird meines Erachtens aber trotzdem nicht gefunden.

Aber hier ist ja auch generell keine Lösung möglich oder?
Oder dürfen die Summen "mit zurücklegen" gebildet werden? Weil ansonsten fällt nach 16=5+5+6 der Rest so oder so flach.

[Namenloser]

Zitat:

Zitat von Neutral General (Beitrag 1318182)

Oder dürfen die Summen "mit zurücklegen" gebildet werden? Weil ansonsten fällt nach 16=5+5+6 der Rest so oder so flach.

Also ich habe das zumindest so verstanden. Aber auch, wenn man "Zurücklegen" nicht erlaubt, bezweifle ich, dass es immer geht. Z.B. bei:

Code:

List<int> MengeA = new List<int>(new int[] { 5, 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int[] { 16, 20 });

Gut, da könnte man jetzt vielleicht sagen, MengeB muss auch absteigend sortiert sein. Habe ich jetzt zugegeben noch kein Gegenbeispiel für gefunden, aber es würde mich doch wundern, wenn es keines gäbe.

[Neutral General]

Zitat:

Zitat von Namenloser (Beitrag 1318185)

Zitat:

Zitat von Neutral General (Beitrag 1318182)

Oder dürfen die Summen "mit zurücklegen" gebildet werden? Weil ansonsten fällt nach 16=5+5+6 der Rest so oder so flach.

Also ich habe das zumindest so verstanden. Aber auch, wenn man "Zurücklegen" nicht erlaubt, bezweifle ich, dass es immer geht. Z.B. bei:

Code:

List<int> MengeA = new List<int>(new int[] { 5, 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int[] { 16, 20 });

Gut, da könnte man jetzt vielleicht sagen, MengeB muss auch absteigend sortiert sein. Habe ich jetzt zugegeben noch kein Gegenbeispiel für gefunden, aber es würde mich doch wundern, wenn es keines gäbe.

Ja da hast du Recht. Aber mit absteigender Sortierung gehts wieder :mrgreen:
Wie gesagt: Ich hab selbst keinen Beweis dass das immer so funktioniert. Und wenn es "mit zurücklegen" ist, dann ist mein Code eh an der Aufgabenstellung vorbei :stupid:

[Namenloser]

Habe doch noch eins gefunden:

Code:

List<int> MengeA = new List<int>(new int[] { 13, 10, 4 });
List<int> MengeB = new List<int>(new int[] { 14, 13 });

Oder auch

Code:

List<int> MengeA = new List<int>(new int[] { 13, 10, 4, 1 });
List<int> MengeB = new List<int>(new int[] { 14, 13, 1 });

Also ohne Backtracking wird es nicht gehen.

[Dejan Vu]

Zitat:

Zitat von BUG (Beitrag 1318111)

Zitat:

Zitat von Dejan Vu (Beitrag 1318108)

Ganz einfach. Dauert nur. Denn es gibt 2^n Teilmengen einer n-elementigen Menge.

Und dir ist klar das 2^1000 eine nicht unbedingt kleine Zahl ist?

Meister, was meinst Du? Ob mir das klar ist? ;-)

Zitat:

Zitat von Namenloser (Beitrag 1318199)

Also ohne Backtracking wird es nicht gehen.

Delphi-Quellcode:

foreach (t in Teilmengen(MengeVonZahlen)) do
  if DieAndereMenge.Enthaelt(t.Summe) then
    Writeln(t.ToString);

Schon mal nicht 'Backtracking'. Bleibt noch 'Teilmengen' bzw. die dort enthaltene Funktion 'NächsteTeilmenge'. Die wird man eleganterweise rekursiv definieren, aber es geht auch iterativ, fällt mir nur gerade nicht ein.

Gibt es in Delphi eigentlich ein Äquivalent zu 'IEnumerable<T>' und etwas wie ein 'yield'?

...
Sind wirklich zwei gleich große Mengen mit identischen Summen gemeint? Das ist interessant. Hier könnt es tatsächlich relativ schnell mit Backtracking gehen. Muss mal nachdenken... Ist aber Freitag, da wird das nix mehr... :-)

[Namenloser]

Zitat:

Zitat von Dejan Vu (Beitrag 1318223)

Zitat:

Zitat von Namenloser (Beitrag 1318199)

Also ohne Backtracking wird es nicht gehen.

Delphi-Quellcode:

foreach (t in Teilmengen(MengeVonZahlen)) do
  if DieAndereMenge.Enthaelt(t.Summe) then
    Writeln(t.ToString);

Schon mal nicht 'Backtracking'. Bleibt noch 'Teilmengen' bzw. die dort enthaltene Funktion 'NächsteTeilmenge'. Die wird man eleganterweise rekursiv definieren, aber es geht auch iterativ, fällt mir nur gerade nicht ein.

Weiß nicht ganz, was du mir damit sagen willst. Falls du nur meinst, dass es auch andere Lösungen als Backtracking gibt: Weiß ich, meine verwendet auch kein Backtracking. Aber von Neutral Generals Ansatz (der ja nicht ganz funktioniert) ausgehend wäre Backtracking der nächste logische Schritt.

[Dejan Vu]

Öh... Ich? Äh..