Finden des kartesischen Produkts mit assoziativen Arrays in PHP

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.

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;
}

Verwendungszweck

$input = array(
    'arm' => array('A', 'B', 'C'),
    'gender' => array('Female', 'Male'),
    'location' => array('Vancouver', 'Calgary'),
);

print_r(cartesian($input));

Hier ist eine optimierte Version der kartesischen Funktion von @ Jon:

function cartesian($input) {
    $result = array(array());

    foreach ($input as $key => $values) {
        $append = array();

        foreach($result as $product) {
            foreach($values as $item) {
                $product[$key] = $item;
                $append[] = $product;
            }
        }

        $result = $append;
    }

    return $result;
}

Lesen Sie mehr über die Mathematik hinter diesem Algorithmus: http://en.wikipedia.org/wiki/Cartesian_product

Sehen Sie sich weitere Beispiele dieses Algorithmus in verschiedenen Sprachen an: https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists

In PHP 7 kann die Antwort von @Serg verkürzt werden zu:

function cartesian(array $input)
{
    $result = [[]];
    foreach ($input as $key => $values) {
        $append = [];
        foreach ($values as $value) {
            foreach ($result as $data) {
                $append[] = $data + [$key => $value];
            }
        }
        $result = $append;
    }

    return $result;
}

Folgendes könnte ich mir einfallen lassen:

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.

inject('a', ['foo', 'bar'])
    =>  [('a', 'foo'), ('b', 'bar')]

Die zip Funktion gilt die inject Funktion für jedes Element in einem Array.

zip(['a', 'b'], ['foo', 'bar'])
    =>  [('a', 'foo'), ('a', 'bar'), ('b', 'foo'), ('b', 'bar')]

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.

zip(zip(['a', 'b'], ['foo', 'bar']), ['42', '76'])
    =>  [('a', 'foo', '42'), ('a', 'foo', '76'), ('a', 'bar', '42'), …]

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.

array_combine(['key1', 'key2', 'key3'], ['a', 'foo', '42'])
    =>  [ key1 : 'a', key2 : 'foo', key3 : '42' ]

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:

function inject($elem, $array) {
    $elem = (array)$elem;
    foreach ($array as &$a) {
        $a = array_merge($elem, (array)$a);
    }
    return $array;
}

function zip($array1, $array2) {
    $prod = array();
    foreach ($array1 as $a) {
        $prod = array_merge($prod, inject($a, $array2));
    }
    return $prod;
}

function cartesian_product($array) {
    $keys = array_keys($array);
    $prod = array_shift($array);
    $prod = array_reduce($array, 'zip', $prod);

    foreach ($prod as &$a) {
        $a = array_combine($keys, $a);
    }
    return $prod;
}

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[];
}

Eine andere Lösung:

function getAllVariations($input) {
    $result = array();
    $cnt = array_product(array_map('count', $input));
    $step = 1;
    foreach ($input as $key=>$array) {
        for ($i=0; $i<$cnt; $i++) {
            foreach ($array as $value) {
                for ($k=0; $k<$step; $k++) {
                    $result[$i+$k][$key] = $value;
                }
                $i += $step;
            }
            $i--;
        }
        $step = $step * count($array);
    }
    return $result;
}

Verwendungszweck:

$input = array(
    'arm' => array('A', 'B', 'C'),
    'gender' => array('Female', 'Male'),
    'location' => array('Vancouver', 'Calgary'),
    'name' => array('Rio', 'Mark')
);

echo "<pre>";
var_dump(getAllVariations($input));

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:

$result = array();
$nm = '';
foreach ($map as $name => $a) {
    if (empty($result)) {
        $result = $a;
        $nm = $name;
        continue;
    }

    $res = array();
    foreach ($result as $r) {
        foreach ($a as $v) {
            $myr = $r;
            $myv = $v;
            if(!is_array($r)) $myr = array($nm => $r);
            if(!is_array($v)) $myv = array($name => $v);

            $res[] = array_merge($myr, $myv);
        }
    }
    $result = $res;
}
echo "<pre>";
print_r($result);