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

Question

我正在寻找是否已经存在特定的算法。 我想在应用程序中使用它，但我也看到它出现在几个 Project Euler< /a> 也有问题。

我正在计算一种特定类型的排列/输出集，其中选择的下一项必须是仅以下一组中的有限选项集中的一个。

例如，假设我有 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

Looking to Implement the algorithm in PHP or 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，您必须自己编写代码。

Answer 2

您可以循环遍历元素。例如，您可以针对您的情况执行以下操作：

var ret = [];
for (var i=0; i<a1.length; i++) {
  for (var j=0; j<a2.length; j++) {
    for (var k=0; k<a3.length; k++) {
      ret.push( [a1[i], a2[j], a3[k]] );
    }
  }
}
// do stuff with ret

但请注意，这非常慢，特别是如果您有很多非常长的数组的数组。对于欧拉项目，通常可以使用一些其他见解，而不是枚举所有内容。

Answer 3

我认为你是对的，它既不是排列也不是组合，因为字符串长度在你的情况下是固定的。请原谅我使用 java [7]，但这是我目前最了解的。

public abstract class AFixedPermutation {
   private char[][] fields;
   private StringBuilder sb = new StringBuilder();
   private int[] callvec;
   private int maxDepth;

   public FixedPermutation(char[][] fields) { 
     this.fields = fields; 

     callvec = new int[fields.length];
     for (int i = 0; i < fields.length; i++) callvec[i] = 0;
     maxDepth = callvec.length - 1;
     recurse(0);
   }

   protected abstract emit(String s);

   private void recurse(int depth) {
     for (int i = 0; i < fields[depth].length; i++) { 
        callvec[depth] = i;
        if (depth == maxDepth) { apply(); }
        else {recurse(depth + 1); }
     }
   }

   private void apply() {
      sb.setLength(0);
      for (int i = 0; i < callvec.length; i++) {
        sb.append(fields[i][callvec[i]]);
      }
      emit(sb.toString());
   }
}

Answer 4

在 Mathematica 中，这本身是作为 Tuples。

Tuples[{{a, b, c}, {d, e, f}, {g, h, i}}]

{{a, d, g}, {a, d, h}, {a, d, i}, {a, e, g}, {a, e, h}, {a, e, i},
 {a, f, g}, {a, f, h}, {a, f, i}, {b, d, g}, {b, d, h}, {b, d, i},
 {b, e, g}, {b, e, h}, {b, e, i}, {b, f, g}, {b, f, h}, {b, f, i},
 {c, d, g}, {c, d, h}, {c, d, i}, {c, e, g}, {c, e, h}, {c, e, i},
 {c, f, g}, {c, f, h}, {c, f, i}}

也可以使用 Outer （广义外部产品）：

Outer[List, {a, b, c}, {d, e, f}, {g, h, i}]

或者通过迭代（Table）：

Table[{x, y, z},
 {x, {a, b, c}},
 {y, {d, e, f}},
 {z, {g, h, i}}
]

或者用递归：

sets[{}, c__] := {{c}}
sets[{x_, r___}, c___] := Join @@ (sets[{r}, c, #] & /@ x)

sets[{{a, b, c}, {d, e, f}, {g, h, i}}]