使用PHP关联数组查找笛卡尔积

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (72)

假设我有一个如下所示的数组:

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

任何帮助,将不胜感激。

提问于
用户回答回答于

这是@ 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;
}

阅读有关此算法背后的数学的更多信息:http//en.wikipedia.org/wiki/Cartesian_product

以不同语言查看此算法的更多示例:https//rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists

用户回答回答于

这是我能想到的:

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)]的,即它注入一个值到一个数组的每个值,返回数组的数组。不要紧,是否ab已经是一个数组,它会始终返回一个二维数组。

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' ]

将其应用于产品中的所有元素可获得所需的结果。

如果您愿意,可以将上述三个函数折叠成一个长语句(这也可以清除误称)。

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

扫码关注云+社区

领取腾讯云代金券