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

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 告诉我这是一个笛卡尔积，这里是一个实现 taken from the PHP website :

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，您必须自己编写代码。