Finden des kartesischen Produkts mit assoziativen Arrays in PHP
Lesezeit: 7 Minuten
Angenommen, ich habe ein Array wie das folgende:
Array
(
[arm] => Array
(
[0] => A
[1] => B
[2] => C
)
[gender] => Array
(
[0] => Female
[1] => Male
)
[location] => Array
(
[0] => Vancouver
[1] => Calgary
)
)
Wie kann ich das kartesische Produkt finden, während ich die Schlüssel des äußeren assoziativen Arrays beibehalte und sie in den inneren verwende? Das Ergebnis des Algorithmus sollte folgendes sein:
Array
(
[0] => Array
(
[arm] => A
[gender] => Female
[location] => Vancouver
)
[1] => Array
(
[arm] => A
[gender] => Female
[location] => Calgary
)
[2] => Array
(
[arm] => A
[gender] => Male
[location] => Vancouver
)
...etc.
Ich habe eine ganze Reihe von kartesischen Produktalgorithmen nachgeschlagen, aber ich bleibe bei den Einzelheiten hängen, wie die assoziativen Schlüssel erhalten bleiben. Der aktuelle Algorithmus, den ich verwende, gibt nur numerische Indizes:
$result = array();
foreach ($map as $a) {
if (empty($result)) {
$result = $a;
continue;
}
$res = array();
foreach ($result as $r) {
foreach ($a as $v) {
$res[] = array_merge((array)$r, (array)$v);
}
}
$result = $res;
}
print_r($result);
Jede Hilfe wäre willkommen.
Verwandte: Werte von n Arrays in PHP verketten (Februar 2010)
– hakre
11. August 2013 um 9:51 Uhr
Dies scheint eine Transponierungsaktion anstelle eines kartesischen Produkts zu sein.
Hier ist eine Lösung, für die ich mich nicht schämen würde.
Begründung
Angenommen, wir haben ein Eingabearray $input mit N Sub-Arrays, wie in Ihrem Beispiel. Jedes Sub-Array hat Cn Artikel, wo n ist sein Index im Inneren $inputund sein Schlüssel ist Kn. Ich verweise auf die iArtikel der nte Untergruppe als Vn,i.
Der folgende Algorithmus kann durch Induktion bewiesen werden, dass er funktioniert (abgesehen von Fehlern):
1) Für N = 1 ist das kartesische Produkt einfach array(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... ) — C1 Artikel insgesamt. Das geht mit einem einfachen foreach.
2) Gehe davon aus $result enthält bereits das kartesische Produkt der ersten N-1 Teilfelder. Das kartesische Produkt von $result und das N-te Teilarray kann auf diese Weise erzeugt werden:
3) In jedem Element (Array) im Inneren $productfügen Sie den Wert hinzu KN => VN,1. Erinnern Sie sich an das resultierende Element (mit dem Mehrwert); Ich werde es als bezeichnen $item.
4a) Für jedes Array darin $product:
4b) Für jeden Wert in der Menge VN,2 ... VN,CNergänzen $product eine Kopie von $itemaber ändern Sie den Wert mit der Taste KN zu VN,m (für alle 2 <= m <= CN).
Die beiden Iterationen 4a (over $product) und 4b (über das N-te Eingangs-Subarray) endet mit $result haben CN Artikel für jeden Artikel, den es vor den Iterationen hatte, also am Ende $result enthält tatsächlich das kartesische Produkt der ersten N Teilarrays.
Daher funktioniert der Algorithmus für jedes N.
Das war schwerer zu schreiben, als es hätte sein sollen. Meine formalen Beweise rosten definitiv ein…
Code
function cartesian($input) {
$result = array();
while (list($key, $values) = each($input)) {
// If a sub-array is empty, it doesn't affect the cartesian product
if (empty($values)) {
continue;
}
// Seeding the product array with the values from the first sub-array
if (empty($result)) {
foreach($values as $value) {
$result[] = array($key => $value);
}
}
else {
// Second and subsequent input sub-arrays work like this:
// 1. In each existing array inside $product, add an item with
// key == $key and value == first item in input sub-array
// 2. Then, for each remaining item in current input sub-array,
// add a copy of each existing array inside $product with
// key == $key and value == first item of input sub-array
// Store all items to be added to $product here; adding them
// inside the foreach will result in an infinite loop
$append = array();
foreach($result as &$product) {
// Do step 1 above. array_shift is not the most efficient, but
// it allows us to iterate over the rest of the items with a
// simple foreach, making the code short and easy to read.
$product[$key] = array_shift($values);
// $product is by reference (that's why the key we added above
// will appear in the end result), so make a copy of it here
$copy = $product;
// Do step 2 above.
foreach($values as $item) {
$copy[$key] = $item;
$append[] = $copy;
}
// Undo the side effecst of array_shift
array_unshift($values, $product[$key]);
}
// Out of the foreach, we can add to $results now
$result = array_merge($result, $append);
}
}
return $result;
}
function inject($elem, $array) {
return array_map(function ($n) use ($elem) { return array_merge((array)$elem, (array)$n); }, $array);
}
function zip($array1, $array2) {
return array_reduce($array1, function ($v, $n) use ($array2) { return array_merge($v, inject($n, $array2)); }, array());
}
function cartesian_product($array) {
$keys = array_keys($array);
$prod = array_shift($array);
$prod = array_reduce($array, 'zip', $prod);
return array_map(function ($n) use ($keys) { return array_combine($keys, $n); }, $prod);
}
(Verwenden Sie unten die Notation für Pseudo-Arrays/Listen/Wörterbücher, da PHP für solche Dinge einfach zu ausführlich ist.)
Die inject Funktion transformiert a, [b] hinein [(a,b)], dh es fügt einen einzelnen Wert in jeden Wert eines Arrays ein und gibt ein Array von Arrays zurück. Egal ob a oder b bereits ein Array ist, wird immer ein zweidimensionales Array zurückgegeben.
Beachten Sie, dass dies tatsächlich ein kartesisches Produkt erzeugt, also zip ist eine leichte Fehlbezeichnung. Wenn Sie diese Funktion einfach nacheinander auf alle Elemente eines Datensatzes anwenden, erhalten Sie das kartesische Produkt für ein Array beliebiger Länge.
Dies enthält nicht die Schlüssel, aber da die Elemente innerhalb der Ergebnismenge alle in der richtigen Reihenfolge sind, können Sie die Schlüssel einfach erneut in das Ergebnis einfügen.
Die Anwendung auf alle Elemente im Produkt führt zum gewünschten Ergebnis.
Sie können die oben genannten drei Funktionen zu einer einzigen langen Anweisung zusammenfassen, wenn Sie dies wünschen (was auch die falschen Bezeichnungen aufklären würde).
Eine “ausgerollte” Version ohne anonyme Funktionen für PHP <= 5.2 sähe so aus:
Warum nicht einen rekursiven Generator verwenden … Speicherprobleme: fast keine
(und es ist wunderschön)
function cartesian($a)
{
if ($a)
{
if($u=array_pop($a))
foreach(cartesian($a)as$p)
foreach($u as$v)
yield $p+[count($p)=>$v];
}
else
yield[];
}
Hinweis: Schlüssel bleiben nicht erhalten; aber es ist ein anfang.
Dies sollte funktionieren (nicht getestet):
function acartesian($a)
{
if ($a)
{
$k=end(array_keys($a));
if($u=array_pop($a))
foreach(acartesian($a)as$p)
foreach($u as$v)
yield $p+[$k=>$v];
}
else
yield[];
}
Was ist die c()-Funktion?
– Pol Dellaiera
21. Dezember 2016 um 22:38 Uhr
@PolDellaiera Hoppla, ich habe die Funktionen selbst nach dem Golfen umbenannt; aber vergessen, die Rekursionsaufrufe zu ändern. Fest.
– Titus
22. Dezember 2016 um 12:26 Uhr
Wie wäre es mit dem Callstack? Was ist die maximale Tiefe von verschachtelten Aufrufen?
– Constantin Galbenu
29. April 2017 um 18:13 Uhr
@ConstantinGALBENU PHP-Standardeinstellungen haben keine Begrenzung; aber es ist ein guter punkt. Vielleicht teste ich eines Tages den Speicherverbrauch.
– Titus
2. Mai 2017 um 9:23 Uhr
Ich habe gefragt, weil in Ihrem Fall der Callstack gleich der Anzahl der Level0-Elemente im Eingabearray ist und dies bei langen Arrays zu einem Problem werden kann.
@PolDellaiera Hoppla, ich habe die Funktionen selbst nach dem Golfen umbenannt; aber vergessen, die Rekursionsaufrufe zu ändern. Fest.
– Titus
22. Dezember 2016 um 12:26 Uhr
Wie wäre es mit dem Callstack? Was ist die maximale Tiefe von verschachtelten Aufrufen?
– Constantin Galbenu
29. April 2017 um 18:13 Uhr
@ConstantinGALBENU PHP-Standardeinstellungen haben keine Begrenzung; aber es ist ein guter punkt. Vielleicht teste ich eines Tages den Speicherverbrauch.
– Titus
2. Mai 2017 um 9:23 Uhr
Ich habe gefragt, weil in Ihrem Fall der Callstack gleich der Anzahl der Level0-Elemente im Eingabearray ist und dies bei langen Arrays zu einem Problem werden kann.
– Constantin Galbenu
2. Mai 2017 um 9:26 Uhr
Sabeen Malik
Ich habe Ihren Code schnell ein wenig angepasst, mein Versuch ist grob, denke ich, aber sehen Sie, ob das so funktioniert, wie Sie es wollen:
Verwandte: Werte von n Arrays in PHP verketten (Februar 2010)
– hakre
11. August 2013 um 9:51 Uhr
Dies scheint eine Transponierungsaktion anstelle eines kartesischen Produkts zu sein.
– XuDing
9. August 2016 um 5:30 Uhr
Schau mal rein kartesisches Produkt von nSPL
– Ihor Burlachenko
27. Februar 2019 um 20:36 Uhr