Erkennen von Zahlenpaaren

[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 von Dejan Vu:

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

[Dejan Vu]

Zitat von BUG:

Zitat von Dejan Vu:

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 von Namenloser:

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 von Dejan Vu:

Zitat von Namenloser:

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..

[ibp]

Zitat von 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.

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?

[JasonDX]

Zitat von lowmax_5:

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.