59

次のような配列があるとします。

Array
(
    [arm] => Array
        (
            [0] => A
            [1] => B
            [2] => C
        )
    [gender] => Array
        (
            [0] => Female
            [1] => Male
        )
    [location] => Array
        (
            [0] => Vancouver
            [1] => Calgary
        )
)

外側の連想配列のキーを保持し、それらを内側の連想配列で使用しながらデカルト積を見つけるにはどうすればよいですか? アルゴリズムの結果は次のようになります。

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.

私はかなりの数のデカルト積アルゴリズムを調べましたが、連想キーを保存する方法の詳細に行き詰まっています。私が使用している現在のアルゴリズムは、数値インデックスのみを提供します。

    $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);

どんな助けでも大歓迎です。

4

10 に答える 10

64

これは、私が恥ずかしがらずに示す解決策です。

根拠

あなたの例のように、サブ配列を$input持つ入力配列があるとします。N各サブ配列にはCn項目があり、nは 内のインデックス$inputであり、キーはKnです。番目のサブ配列iの 番目の項目を と呼びます。nVn,i

以下のアルゴリズムは、推論によって (バグを除いて) 動作することが証明されます。

1) N = 1 の場合、デカルト積は単純にarray(0 => array(K1 => V1,1), 1 => array(K1 => V1,2), ... )-- 合計で C1 項目です。これは、単純なforeach.

$result2)が最初の N-1 サブアレイのデカルト積を既に保持していると仮定します。と N 番目のサブ配列のデカルト積は$result、次のように生成できます。

3) 内$productの各項目 (配列) に、値を追加しますKN => VN,1。結果のアイテムを（付加価値を付けて）覚えておいてください。と呼びます$item。

4a) 内部の各配列について$product:

4b) セット内の各値について、 のコピーにVN,2 ... VN,CN追加しますが、キーを使用して値を(すべての) に変更します。$product$itemKNVN,m2 <= m <= CN

2 つの反復 4a (オーバー$product) と 4b (N 番目の入力サブ配列に対して) は、反復の前に持っていたすべてのアイテムのアイテムを$result持つことになり、最終的には最初の N サブ配列のデカルト積が実際に含まれます。CN$result

したがって、アルゴリズムは任意の N に対して機能します。

これは、必要以上に書くのが困難でした。私の正式な証明は間違いなく錆びています...

コード

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

使用法

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

print_r(cartesian($input));
于 2011-06-11T00:45:22.910 に答える
8

これが私が思いつくことができるものです：

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

（PHPは単純に冗長すぎるため、以下の疑似配列/リスト/辞書表記を使用します。）

inject関数はに変換a, [b]されます。[(a,b)]つまり、配列の各値に単一の値を挿入し、配列の配列を返します。a配列であるかどうかは関係ありませんb。常に2次元配列を返します。

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

この関数は、配列内の各要素に関数をzip適用します。inject

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

これは実際にはデカルト積を生成するためzip、わずかな誤称であることに注意してください。この関数をデータセット内のすべての要素に連続して適用するだけで、任意の長さの配列のデカルト積が得られます。

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

これにはキーは含まれていませんが、要素はすべて結果セット内で順番に並んでいるため、結果にキーを再挿入するだけで済みます。

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

これを製品のすべての要素に適用すると、望ましい結果が得られます。

必要に応じて、上記の3つの関数を1つの長いステートメントにまとめることができます（これにより、誤称も解消されます）。

PHP <= 5.2の無名関数のない「展開された」バージョンは、次のようになります。

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;
}
于 2011-06-11T03:19:51.163 に答える
8

再帰ジェネレーターを使用しないのはなぜですか...メモリの問題：ほとんどありません
（そしてそれは美しいです）

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

注: これはキーを保持しません。しかし、それは始まりです。

これは行う必要があります（テストされていません）：

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[];
}
于 2016-08-26T20:15:49.397 に答える
3

別の解決策：

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

使用法：

$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));
于 2013-04-13T12:06:47.860 に答える
2

私はすぐにあなたのコードを少し調整しました、私の試みは粗雑だと思いますが、これがあなたが望むように機能するかどうか見てください:

$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);
于 2011-06-10T21:36:02.217 に答える
2

メモリ消費が重要な場合、または最終的にすべての組み合わせが必要ない場合は、反復子を使用して一度に 1 つの組み合わせを生成できます。すべての組み合わせが必要な場合は、 を使用できますiterator_to_array。

function cartezianIterator($inputArray)
{
    $maximumPosition = array_map('count', $inputArray);
    $position = array_pad([], count($inputArray), 0);

    while (false !== ($item = buildItemAtPosition($inputArray, $position))) {

        yield $item;

        $position = incrementPosition($position, $maximumPosition);
    }
}

function buildItemAtPosition($inputArray, $positions)
{
    if ($positions[0] >= count($inputArray[0])) {
        return false;
    }

    $item = [];
    foreach ($inputArray as $rowIndex => $row) {
        $position = $positions[$rowIndex];

        $item[] = $row[$position];
    }

    return $item;
}

function incrementPosition($position, $maximumPosition)
{
    $digitToIncrement = count($position) - 1;

    do {
        $position[$digitToIncrement]++;

        if ($position[$digitToIncrement] < $maximumPosition[$digitToIncrement] || 0 === $digitToIncrement) {
            //no overflow
            break;
        }

        //overflow, reset to zero and increment parent digit
        $position[$digitToIncrement] = 0;

        $digitToIncrement--;
    } while ($digitToIncrement >= 0);

    return $position;
}

次に、一度に 1 つのソリューションを取得するには、次のようにforeachまたはを使用できます。next

$iterator = cartezianIterator($inputArray);

//of course, you need to do something with the result...
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);
$combination = next($iterator);

いくつかの組み合わせしか必要ない場合、このソリューションは非常に高速です。また、メモリ消費量は非常に少ないです (arrayいくつかの を格納するためにフラットを使用しますintegers)。

注: 再帰関数は使用されません。

于 2017-04-30T07:15:32.913 に答える
1

これを行うためにデータベースを使用しないのはなぜですか?

MySQLでは簡単です..

table arm
   id integer primary key
   label char

table gender
   id integer primary key
   gender enum('male','female')

table location
   id integer primary key
   city varchar(255)

次に、クエリを実行します

$query = mysql_query(" 
  SELECT a.label, g.gender, l.city
  FROM arm a
  CROSS JOIN gender g
  CROSS JOIN location l
  ORDER BY a.id
") or die("Could not execute query");

while($row = mysql_fetch_array($query) )
{
   ....
}

そしてそれを読んでください：

于 2011-06-10T21:15:58.937 に答える