Kombination aus zwei Arrays bilden

[Antilogarithm]

Hallo zusammen,

ich komme leider nicht weiter, bestimmt kann mir von euch jemand auf die Sprünge helfen.

Ich habe zwei Arrays

$aItems = array(
	array( 'item' => 'item1'),
	array( 'item' => 'item2'),
	array( 'item' => 'item3')
);

$aVendors = array(
	array( 'vendor' => 'shopA'),
	array( 'vendor' => 'shopB'),
	array( 'vendor' => 'shopC')
);

Mit diesen beiden Arrays sollen nun alle möglichen Kombinationen gebildet werden, so dass man eine solche Liste erhält:

id; item; vendor
-----------------
1; item1; shopA
1; item2; shopA
1; item3; shopA

2; item1; shopB
2; item2; shopA
2; item3; shopA

3; item1; shopC
3; item2; shopA
3; item3; shopA

4; item1; shopA
4; item2; shopB
4; item3; shopA

5; item1; shopB
5; item2; shopB
5; item3; shopA

6; item1; shopC
6; item2; shopB
6; item3; shopA

7; item1; shopA
7; item2; shopC
7; item3; shopA

[...]

26; item1; shopB
26; item2; shopC
26; item3; shopC

27; item1; shopC
27; item2; shopC
27; item3; shopC

Hierzu habe ich versucht den entsprechenden PHP Code zu schreiben, leider funktioniert es so nicht wie gewünscht.
Hier mal mein fehlerhafter Code:

$cItems = count($aItems);
$cVendors = count($aVendors);
$comibinations = pow($cVendors, $cItems);

$vid = -1;
for ($id = 1; $id <= $comibinations; $id++)
{
	echo "<br>";
	if ($vid < $cVendors-1)
	{
		$vid++;
	}
	else
	{
		$vid = 0;
	}
	for ($i = 0; $i <= $cItems-1; $i++)
	{
		echo $id . "; " . $aItems[$i]['item'] . "; " . $aVendors[$vid]['vendor'] . "<br>";
		$rows++;
	}
}

echo "<br>Kombinationen: " . $id . " - Zeilen: " . $rows;

Mein Ergebnis sieht so aus:

1; item1; shopA
1; item2; shopA
1; item3; shopA

2; item1; shopB
2; item2; shopB
2; item3; shopB

3; item1; shopC
3; item2; shopC
3; item3; shopC

4; item1; shopA
4; item2; shopA
4; item3; shopA

[...]

26; item1; shopB
26; item2; shopB
26; item3; shopB

27; item1; shopC
27; item2; shopC
27; item3; shopC

Wie muss ich meinen Code umschreiben, damit ich das gewünschte Ergebnis bekomme?
Schönen Dank schon mal im Voraus für die Hilfe!

PS: Ja, es geht um eine PHP Umsetzung des ersten Teils der SQL Lösung von Yaslaw hier:
http://www.tutorials.de/relationale...orgehensweise-kombinationen-durchrechnen.html

 

[chmee]

hast Du es schon mit foreach() probiert?
(In Deinem Fall vielleicht nur innere mit äußerer Schleife tauschen? bzw. deren Array-Variablen?)

mfg chmee

 

[Antilogarithm]

Soo, ich habe eine Lösung, aber bestimmt geht das eleganter. Hat jemand einen Vorschlag?
Hier meine Lösung:

function vid ($item, $vid)
{
	global $cItems;
	global $cVendors;
	
	if ($vid[$item] < $cVendors-1)
	{
		$vid[$item]++;
	}
	else
	{
		$vid[$item] = 0;
		if ($item < $cItems)
		{
			++$item;
			$vid = vid ($item, $vid);
		}
	}
	return $vid;
}


$cItems = count($aItems);
$cVendors = count($aVendors);
$comibinations = pow($cVendors, $cItems);

foreach ($aItems as $key => $value)
{
	$vid[$key] = 0;
}
$vid[0] = -1;
for ($id = 1; $id <= $comibinations; $id++)
{
	echo "<br>";
	$item = 0;
	$vid = vid ($item, $vid);
	
	for ($i = 0; $i <= $cItems-1; $i++)
	{
		echo $id . "; " . $aItems[$i]['item'] . "; " . $aVendors[$vid[$i]]['vendor'] . "<br>";
		$rows++;
	}
}

echo "<br>Kombinationen: " . --$id . " - Zeilen: " . $rows;

 

[Antilogarithm]

Ich habe gerade mal ein paar Testberechnungen gemacht und muss feststellen, dass die Laufzeiten erheblich sind. Bei nur 8 Items von 9 Vendors kommt man auf 43.046.721 Kombinationen und 344.373.768 Zeilen. Das Skript braucht auf meinem Sever 166 Sekunden dafür.

Das ganze soll aber später durchgeführt werden für Arrays mit ca. 100 Items von ca. 200 Händlern.

Hat jemand einen Vorschlag, wie man das beschleunigen kann?
Wäre es vielleicht sinnvoller das in Pearl zu machen, oder kann man MySQL zur Hilfe nehmen?

 

[Parantatatam]

Vielleicht kann man dein Problem auch anders lösen, wenn wir wissen, was du damit erreichen willst.

 

[Antilogarithm]

Die eigentliche Aufgabenstellung habe ich hier beschrieben:
http://www.tutorials.de/relationale...orgehensweise-kombinationen-durchrechnen.html

Yaslaw hat dazu auch eine super Lösung gepostet. Dummerweise hatte ich dort geschrieben, dass ich nach einer reinen SQL Lösung suche. Das war etwas voreilig von mir formuliert.
Die von Yaslaw erdachte Lösung in SQL geht das Problem so an, dass zunächst eine Zwischentabelle erstellt wird, die alle möglichen Kombinationen enthält. Anschließend werden daraus die Kombinationsfälle ausgewählt, die den Vorgaben entsprechen.
Im dritten Schritt wird dann die eigentliche Frage per SQL auf diese zweite Zwischentabelle gelöst. Dieser letzte Schritt läuft erstaunlich schnell ab. Aber das Erstellen der beiden Zwischentabellen ist sehr langwierig. Insbesondere, da die erste Tabelle eben alle theoretisch möglichen Kombinationen enthält.

Ich habe mal ein Beispiel mit 6 Teilen von 10 Händlern durchgerechnet. Da enthält die erste Zwischentabelle 10^6 * 6 also 6.000.000 Einträge. Darunter sind aber "nur" 1.843.200 relevante Einträge, die alle Randbedingungen erfüllen.
Das Anlegen der ersten Zwischentabelle in SQL mit den 6 Millionen Einträgen wollte ich umgehen, da es auch sehr lange dauert und lieber in PHP (oder von mir aus auch in einer anderen Sprache) direkt eine Tabelle nur mit den tatsächlich benötigten 1,8 Millionen Einträgen erstellen. Aber damit ich entscheiden kann, welche Kombinationsmöglichkeit relevant ist, muss ich die theoretisch möglichen Kombinationen durchlaufen.
Hmm, jetzt wo ich das hier schreibe, fällt mir auf, dass man einen Kombinations-Durchlauf sofort abbrechen und zur nächsten Kombination springen kann, sobald eine item-vendor Kombination die Randbedingungen nicht erfüllt. Das muss ich mal ausprobieren, wieviel das bringt.

Aber wie gesagt, später sollen Fälle berechnet werden, bei denen es um 100 Items von ca. 200 Händlern geht. Das wäre also eine Tabelle mit 200^100 * 100 = 1.26765060022823e+232 Einträgen.
Davon ist letztlich zwar nur ein Bruchteil relevant, der alle Randbedingungen erfüllt, aber bei den Laufzeiten würde das Durchtesten aller möglichen Kombinationen ja Tage dauern.

 

[chmee]

Kann man die Frage nicht "umwandeln" in ein Graphenproblem, so in Richtung "Königsberger Brückenproblem" oder so? Wenn man Preis, Produkt und Verfügbarkeit als Koordinaten in einem kartesianischen K-System mißbraucht? Und dann abhängig von der Frage (brauche A, B und C) die kürzeste (geschlossene) Strecke sucht?

Ich bin in Graphen recht unwissend - ich wollte nur nen alternativen Denkansatz anstoßen Grad nochmal den Begriff [wiki]Kombinatorik[/wiki] in Wiki gelesen. Da werden weitere Teilbereiche genannt.


mfg chmee

 

[chmee]

Noch ein kurzer Gedanke, um diese Rechenexplosion zu minieren. Ist es überhaupt nötig, es kombinatorisch zu lösen? Man zerteilt die Frage in Teilfragen.

(A1) Kann ein Anbieter alle Produkte liefern?
(A2) Können mehrere Anbieter alle Produkte liefern?
(B1) Kann ein Anbieter n-1 Produkte liefern? (etc pp)
(B2) Liste aller Anbieter, die n-m!=0 Produkte liefern können? (per count)
(C) Von jedem Produkt das preiswerteste Angebot raussuchen?

(D) Ist aus der Kombination dieser Antworten schon das Ideal erstellbar?

mfg chmee

 

[Antilogarithm]

Danke chmee,

zu deinem zweiten Vorschlag hatte ich mir auch schon Gedanken gemacht. Es ist sicherlich sinnvoll die Menge der Händler möglichst bereits im Vorfeld zu reduzieren. Allerdings geht die Anzahl der Händler nur als Basis in die Berechnung der Kombinationsmenge ein, die Anzahl der Items aber als Exponent und als Multiplikator. Die Menge der zu betrachtenden Kombinationen werden also vor allem durch die Anzahl der Items beeinflusst.

Die Idee die Aufgabe als Graphenproblem zu betrachten scheint mir sinnvoll zu sein. Allerdings habe ich Null Ahnung von dem Thema.
Wenn ich es richtig verstehe, ist mein Problem gut mit dem 'Problem des Handlungsreisenden' (auch Rundreiseproblem, engl. Traveling Salesman Problem oder Traveling Salesperson Problem (TSP)) vergleichbar. https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Aber wie geht man so etwas praktisch an?
Ich habe zwar jede Menge theoretische Beschreibungen gefunden, aber wie setzt man diese Theorien in Programmcode um?


Schönen Gruß