算法 - 从必须按顺序选择的项目生成所有组合

Question

我想找出一个特定的算法是否已经存在.我想在一个应用程序中使用它,但我也看到这也出现在几个Project Euler问题中.

我正在寻找一种特定类型的置换/输出集,其中所选择的下一个项必须是仅来自以下集中的有限选项集中的一个.

例如,假设我有3个阵列

$a1 = array("a", "b", "c");
$a2 = array("d", "e", "f");
$a3 = array("g", "h", "i");

我希望生成一个序列的所有可能性,每个数组包含最多1个元素,按顺序选择.也就是说作为输出,我想看到:

adg aeg afg
adh aeh afh
adi aei afi

bdg beg bfg 
bdh beh bfh
bdi bei bfi

cdg ceg cfg
cdh ceh cfh
cdi cei cfi

希望在PHP或Javascript中实现该算法.实质上,它将通过包含可变数量元素的可变数量的数组,并输出可以按顺序发生的所有序列的可能性.

这存在吗？

如果是这样,它叫什么？从技术上讲,这不是一个排列,也不是我所知道的两者的组合.

编辑:Daniel Fischer告诉我这是一个笛卡尔积,这是一个从PHP网站获得的实现:

function array_cartesian_product($arrays)
{
    $result = array();
    $arrays = array_values($arrays);
    $sizeIn = sizeof($arrays);
    $size = $sizeIn > 0 ? 1 : 0;
    foreach ($arrays as $array)
        $size = $size * sizeof($array);
    for ($i = 0; $i < $size; $i ++)
    {
        $result[$i] = array();
        for ($j = 0; $j < $sizeIn; $j ++)
            array_push($result[$i], current($arrays[$j]));
        for ($j = ($sizeIn -1); $j >= 0; $j --)
        {
            if (next($arrays[$j]))
                break;
            elseif (isset ($arrays[$j]))
                reset($arrays[$j]);
        }
    }
    return $result;
}

Answer 1

如果从每个列表/数组中选择一个项目，更准确地说是笛卡尔积的元素列表，则它是笛卡尔积。对于列表，它位于 Haskell 的标准库中：

Prelude> sequence ["abc","def","ghi"]
["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh"
,"bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]

我认为对于 PHP 或 Javascript，你必须自己编写代码。