algorithm - 笛卡尔/组合算法(同时保持顺序)

Question

由于我不太了解这些类型算法的语言(即如何用谷歌搜索这个)，我将只演示我正在寻找的内容:

我有三个数组(源数组的长度不相等):

$array1 = array('A', 'B', 'C', 'D');
$array2 = array('x', 'y', 'z');
$array3 = array('1', '2', '3');

我想要这些数组的所有可能组合，其中:

• 从每个源数组中提取的元素不超过一个。
• array1、array2、array3 的顺序永远不会被破坏(ABC 总是在 xyz 之前总是在 123 之前)。

所以结果是:

array(
  array('A', 'x', '1'),
  array('A', 'x', '2'),
  array('A', 'x', '3'),
  array('A', 'y', '1'),
  // etc ...

  // But I also need all the partial sets, as long as the rule about
  // ordering isn't broken i.e.:
  array('B'),
  array('B', 'x'),
  array('B', 'x', '1'),
  array('x'),
  array('x', '1'),
  array('1'),
);

结果的顺序对我来说并不重要。

在 php 中工作，但类似的语言或伪代码当然没问题。或者我只是想知道我应该关注哪些特定类型的排列/组合算法。

Answer 1

我会说这些是笛卡尔积。生成它们非常容易。

• 对于固定数量的数组(在 Perl 中):

  for my $a(@arrayA) {
    for my $b(@arrayB) {
      push @result, [$a, $b];
    }
  }
  

• 一般过程:假设 @partial 是 A1 x A2 x ... x An 的笛卡尔积数组，我们想要 A1 x ... x An x An+1

  for my $a(@partial) {
    for my $b(@An_plus_1) {
      push @result, [@$a, $b];
    }
  }
  

  这显然需要遍历所有数组。

现在，如果您还想省略集合中的某些元素，只需稍微扭曲一下即可。在第一种方法中，您可以向每个数组添加另一个元素(undef 是显而易见的选择，但任何东西都可以)，然后在结果集中过滤掉这些元素。在第二种方法中，它更简单:您只需将 @partial 和 map { [$_] } @An_plus_1 添加到结果(或者，用英语，所有A1 x ... x An 的部分笛卡尔积加上新集合的元素组成的单个元素集产生的集合。