Maximum verschiedener Paarungen ermitteln.

[Texter mit x]

Hallo,

Gegeben sind zwei Gruppen von Elementen mit variabler Anzahl von Elementen und ein Operator(O). Das Ergebnis der Rechnung [Element(aus Gruppe 1) Operator Element(aus Gruppe 2)] hat den Wertebereich Null bis Eins.

Gesucht ist das Maximum der Summen aller Berechnungen, wobei jedes Element nur einmal einbezogen werden darf (bei ungleicher Elementanzahl in den Gruppen bleiben also Elemente einer Gruppe im Ergebnis unberücksichtigt).

Beispiel:
Gruppe 1: A, B, C, D
Gruppe 2: X, Y, Z

Im ersten Zwischenschritt würden alle Paarungen durchgegangen:
AOX, AOY, ..., DOZ (aber nicht AOA, AOB, ..., ZOZ)
Code:

  
$gruppe_1 = array(A, B, C, D);  
$gruppe_2 = array(X, Y, Z);  
$zw_ergebnis = array();  
  
$count_1 = count($gruppe_1) - 1;  
$count_2 = count($gruppe_2) - 1;  
  
for($z1 = $count_1; $z1 >= 0; $z1--) {  
  for($z2 = $count_2; $z2 >= 0; $z2--) {  
    $zw_ergebnis[$z1][$z2]) = operator_O($gruppe_1[$z1], $gruppe_2[$z2]);  
  }  
}  

Nun das eigentliche Problem:
Wie kann ich alle Summen aller Berechnungen ermitteln, ohne, daß ein Element zwei mal einbezogen wird?

AOX + BOY + COZ
AOX + BOY + DOZ
AOX + BOZ + COY
AOX + BOZ + DOY

BOX + AOY + COZ
...
Ich finde keine beschreibbare Systematik die den unterschiedlichen Elementanzahlen gerecht wird.

[Sven Rautenberg]

Moin!

Wie kann ich alle Summen aller Berechnungen ermitteln, ohne, daß ein Element zwei mal einbezogen wird?

Du wählst dir die kleinere der beiden Gruppen und ordnest jedem der Elemente ein Element aus der anderen Gruppe zu.

Das läuft darauf hinaus, dass du alle möglichen Anordnungen der größeren Gruppe bildest, und einfach nach der Anzahl der Elemente der kleineren Gruppe abschneidest.

Sprich: Für dein X setzt du nacheinander A, B, C und D als Partner. Für jeden dieser Partner setzt du bei AOX für Y jeweils B, C und D. Für Z bleiben bei BOY dann noch C und D.

Sozusagen FOR-Schleife, die ein Element überspringt, wenn es schon benutzt ist.

- Sven Rautenberg

[Texter mit x]

Sozusagen

Hmm, so weit, zu sagen, was ich so machen will, war ich auch schon.

Mit FOR-Schleifen und überspringen ist es aber nicht getan. Man müßte außer überspringen auch noch wiederholen. Was soll dann "for" sein? Oder habe ich den Kern deiner Überlegung nicht mitbekommen?

Was abschneiden will ich auch nicht, jede Summe wird zwar nur aus so vielen Summanden gebildet wie die kleinste Gruppe Elemente hat aber es sollen alle Variationen berücksichtigt werden.

Anderes Beispiel, der Übersichtlichkeit halber mit Zahlen für die zweite Gruppe und ohne Operator O:
A1, A2, A3, A4, A5
B1, B2, B3, B4, B5
C1, C2, C3, C4, C5

rauskommen soll:
A1+B2+C3
A1+B2+C4
A1+B2+C5
A1+B3+C2
A1+B3+C4
A1+B3+C5
A1+B4+C2
A1+B4+C3
A1+B4+C5
A1+B5+C2
A1+B5+C3
A1+B5+C4
A2...
A3...
A4...
A5...

[Sven Rautenberg]

Moin!

Anderes Beispiel, der Übersichtlichkeit halber mit Zahlen für die zweite Gruppe und ohne Operator O:
A1, A2, A3, A4, A5
B1, B2, B3, B4, B5
C1, C2, C3, C4, C5

rauskommen soll:
A1+B2+C3
A1+B2+C4
A1+B2+C5
A1+B3+C2
A1+B3+C4
A1+B3+C5
A1+B4+C2
A1+B4+C3
A1+B4+C5
A1+B5+C2
A1+B5+C3
A1+B5+C4
A2...
A3...
A4...
A5...

Das ist genau, was ich meinte. Deine kleinere Gruppe in diesem neuen Beispiel sind die Buchstaben (A-C). Denen werden drei aus fünf Zahlen zugeordnet, und zwar regelmäßig: Nimm die erste Zahl für A und spiele die restlichen Zahlen auf den Folgepositionen durch. Nimm die zweite Zahl für A und spiele die restlichen Zahlen auf den Folgepositionen durch...

Klingt sehr rekursiv, das ganze, denn für B ist es nicht anders: Nimm die erste Zahl (der restlichen Zahlen) für B und spiele die restlichen Zahlen auf den Folgepositionen durch.

- Sven Rautenberg

[Texter mit x]

Nimm die erste Zahl für A und spiele die restlichen Zahlen auf den Folgepositionen durch. Nimm die zweite Zahl für A und spiele die restlichen Zahlen auf den Folgepositionen durch...

Durchspielen "sozusagen"?

Denken kann ich das, wie meine Liste vermuten lassen könnte. Was ich nicht kann ist, das in vernünftige Regeln umzusetzen.

Klingt sehr rekursiv, das ganze, denn für B ist es nicht anders: Nimm die erste Zahl (der restlichen Zahlen) für B und spiele die restlichen Zahlen auf den Folgepositionen durch.

Das ist doch nicht nur mit for-Schleifen zu machen, weil die Anzahl der nötigen for-Schleifen von der Menge der Elmente abhängen würde, oder?

Oder doch nicht?!
Durchgang erste for-Schleife A1, übrig bleibt:
B2, B3, B4, B5
C2, C3, C4, C5
Durchgang zweite for-Schleife B2, übrig bleibt:
C3, C4, C5 (wie addieren? mit dritter for-Schleife?)
Durchgang zweite for-Schleife B3, übrig bleibt:
C4, C5
Jedenfalls dann, wenn man mit den Zählern aus den for-Schleifen arbeitet. Es fehlt C2. Um das zu erfassen, müßte man die Schleife "wiederholen". Oder man zählt von vorn und "überspringt" wie Du es schriebst.

Die erste for-Schleife muß so oft durchlaufen werden, wie die kleinere Anzahl Elemente.
Darin muß die zweite for-Schleife so oft durchlaufen werden, wie die größere Anzahl Elemente - 1.
Die dritte for-Schleife muß so oft durchlaufen werden, wie die größere Anzahl Elemente. Dabei müssen die "Position" ausgelassen werden, in der sich die erste und zweite for-Schleife gerade befindet. Effektiv also "größere Anzahl Elemente - 2" Durchgänge.

Ich werde mich noch daran versuchen aber jetzt gehe ich schlafen.
Ich habe es mir anders überlegt.

  
$summen = array();  
for ($z1 = $count_1; $z1 >= 0; $z1--) {  
  for ($z2 = $count_2 - 1; $z2 >= 0; $z2--) {  
    $zw_2 = $zw_ergebnis[$z1][$count_1] + $zw_ergebnis[$z1][$z2];  
    for ($z3 = $count_2; $z3 >= 0; $z3--) {  
      if (($z3 != $z1) AND ($z3 != $z2)) {  
        $summen[] = $zw_2 + $zw_ergebnis[$z3][$z2];  
      }  
    }  
  }  
}  
$max = max($summen);  

So in etwa, fehlerbehaftet, wobei per Definition die erste Gruppe die kleinere oder gleichgroße ist. Aber jetzt gehe ich schlafen, um die korrekten Indizes kümmere ich mich morgen.

[Vinzenz Mai]

Hallo,

Mit FOR-Schleifen und überspringen ist es aber nicht getan. Man müßte außer überspringen auch noch wiederholen.

wieso wiederholen, das hast Du doch ausgeschlossen.

Was abschneiden will ich auch nicht, jede Summe wird zwar nur aus so vielen Summanden gebildet wie die kleinste Gruppe Elemente hat aber es sollen alle Variationen berücksichtigt werden.

1. Schritt:
Du hast (Mächtigkeit der kleineren Menge := k) aus (Mächtigkeit der größeren Menge := n) Möglichkeiten k-Tupel aus disjunkten Elementen der größeren Menge zu bilden.

2. Schritt:
Da die Reihenfolge relevant ist, ergeben sich für jeden k-Tupel k! verschiedene Anordnungen,

alles in allem hast Du also eine Variation ohne Zurücklegen von k aus n Elementen (rein auf Deine gewünschte Anzahl bezogen).

Freundliche Grüße

Vinzenz

[Texter mit x]

wieso wiederholen, das hast Du doch ausgeschlossen.

Ich habe ausgeschlossen, daß sich bei der Berechnung einer Summe ein Element wiederholt. Die Wiederholung von Berechnungen mit gleichen (im Beispiel 12x, z.B. A1) und anderen (+B2+C3 bzw. +B2+C4) Elementen ist aber nötig. "Klingt sehr rekursiv, das ganze," wie Sven Rautenberg schreibt.

1. Schritt:
   Du hast (Mächtigkeit der kleineren Menge := k) aus (Mächtigkeit der größeren Menge := n) Möglichkeiten k-Tupel aus disjunkten Elementen der größeren Menge zu bilden.

2. Schritt:
   Da die Reihenfolge relevant ist, ergeben sich für jeden k-Tupel k! verschiedene Anordnungen,

1. Wohin führen die Schritte? Auf einen Lösungsweg, wo ich wissen muß, wieviele Summen es gibt, bin ich noch nicht gekommen.
2. Die Reihenfolge ist mir egal, Summaden kann man vertauschen.

alles in allem hast Du also eine Variation ohne Zurücklegen von k aus n Elementen (rein auf Deine gewünschte Anzahl bezogen).

Mir Fällt gerade ein Witz ein. Ein Mathematiker bekommt eine Aufgabe zu lösen, sie lautet 2 + 2. Nach einem Tag kommt er mit einem Bündel Papier wieder und berichtet: Ich kann aufzeigen, daß eine Lösung existiert.

[Vinzenz Mai]

Hallo

1. Schritt:
   Du hast (Mächtigkeit der kleineren Menge := k) aus (Mächtigkeit der größeren Menge := n) Möglichkeiten k-Tupel aus disjunkten Elementen der größeren Menge zu bilden.

2. Schritt:
   Da die Reihenfolge relevant ist, ergeben sich für jeden k-Tupel k! verschiedene Anordnungen,

1. Wohin führen die Schritte? Auf einen Lösungsweg, wo ich wissen muß, wieviele Summen es gibt, bin ich noch nicht gekommen.
2. Die Reihenfolge ist mir egal, Summaden kann man vertauschen.

Du hast meinen Vorschlag nicht verstanden :-(

Gehen wir von Deinem Beispiel aus:

Menge K = {A, B, C}, somit k = 3
Menge N = {1, 2, 3, 4, 5}, somit n = 5

Zähle im Schritt 1 (äußere Schleife) die verschiedenen Möglichkeiten durch, drei Elemente aus der Menge N zu entnehmen (ohne Berücksichtigung der Reihenfolge):

3 4 5
2 3 4
2 3 5
...

Dafür gäbe es ein ganz einfaches System. Da ein Element entweder in der Auswahl enthalten ist oder nicht und es genau 5 Elemente gibt, kannst Du
vom kleinsten Wert 00111 bis zum größten Wert 11100 im Zweiersystem durchzählen und nur Werte mit drei Einsen nehmen.

In der inneren Schleife, d.h. für jede Auswahl bildest Du alle möglichen
Permutationen der Auswahl, für die erste Auswahl 3, 4, 5 wären das
(k = 3, somit 3! = 6 Permutationen):

A3 + B4 + C5
A3 + B5 + C4
A4 + B3 + C5
A4 + B5 + C3
A5 + B3 + C4
A5 + B4 + C3

d.h. für die innere Schleife benötigst Du ein System, das die k! Permutationen
von k Elementen durchläuft.

Anschließend das gleiche Spielchen mit den 3! Permutationen von 2 3 5, ...
bis zur letzten Auswahl aus der äußeren Schleife.

alles in allem hast Du also eine Variation ohne Zurücklegen von k aus n Elementen (rein auf Deine gewünschte Anzahl bezogen).
Mir Fällt gerade ein Witz ein. Ein Mathematiker bekommt eine Aufgabe zu lösen, sie lautet 2 + 2. Nach einem Tag kommt er mit einem Bündel Papier wieder und berichtet: Ich kann aufzeigen, daß eine Lösung existiert.

Es ist eine gute Idee zu kontrollieren, ob man so viele verschiedene Summen
berechnet hat, wie es gibt :-)

Und genauso wie der Mathematiker die einfache Lösung 4 übersieht, so übersiehst Du den konkreten zweistufigen Lösungsweg, der in  meinen Hinweisen
enthalten ist.

Freundliche Grüße

Vinzenz

[Vinzenz Mai]

Hallo

Gehen wir von Deinem Beispiel aus:

Menge K = {A, B, C}, somit k = 3
Menge N = {1, 2, 3, 4, 5}, somit n = 5

Zähle im Schritt 1 (äußere Schleife) die verschiedenen Möglichkeiten durch, drei Elemente aus der Menge N zu entnehmen (ohne Berücksichtigung der Reihenfolge):

3 4 5
2 3 4
2 3 5
...

Dafür gäbe es ein ganz einfaches System. Da ein Element entweder in der Auswahl enthalten ist oder nicht und es genau 5 Elemente gibt, kannst Du
vom kleinsten Wert 00111 bis zum größten Wert 11100 im Zweiersystem durchzählen und nur Werte mit drei Einsen nehmen.

Grundsätzlich geht es also um das Zählen von Bits und da könntest Du Dir
folgendes Archivposting (und
folgende) ansehen. Es gibt komplizierte und einfache Methoden. Ich denke
nicht, dass Du hier auf Performance achten musst.

Sehr nett der Vorschlag von [Chris B.].

In der inneren Schleife, d.h. für jede Auswahl bildest Du alle möglichen
Permutationen der Auswahl, für die erste Auswahl 3, 4, 5 wären das
(k = 3, somit 3! = 6 Permutationen):

einen Ansatz, wie Du das angehen kannst, findest Du in diesem Archivposting.

Das sollte eigentlich genügen, um auf eine systematische Lösung für beliebige
Mengen an Ausgangswerten zu kommen.

Freundliche Grüße

Vinzenz

[Texter mit x]

Ich denke ich habe verstanden wo es hingeht. Wir suchen alle Koordinatenkombinationen des Arrays zusammen.

Die äußere Schleife wäre:

  
$ug = str_pad('', $count_1 + 1, '1');  
$og = bindec(str_pad($ug, $count_2 + 1, '0'));  
$ug = bindec($ug);  
  
for ($z1 = $ug; $z1 <= $og; $z1++) {  
  if (substr_count(decbin($z1), '1') == 3) {  
    echo decbin($z1).'<br>';  
  }  
}  

Statt dem "echo decbin($z1).'<br>';" muß dann die innere Schleife hin, auf die ich noch kommen muß.

Wie am Ende aus den mit 1 "markirten" Koordinatenposition der Index für das Array werden soll (mit vernünftigem Aufwand), ist mir aber schleierhaft.

Und genauso wie der Mathematiker die einfache Lösung 4 übersieht, so übersiehst Du den konkreten zweistufigen Lösungsweg, der in  meinen Hinweisen
enthalten ist.

Dem Matematike, der die einfache Lösung 4 übersieht, hilft der Hinweis "Du hast zwei Werte und bei dem Operator darf man die Werte vertauschen, also kann man es auf 2! Arten lösen" wahrscheinlich auch nicht weiter.