2

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

我有一个三个数组（源数组的长度不相等）：

$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 中工作，但类似的语言或伪代码当然可以。或者我只是对我应该查看哪些特定类型的排列/组合算法提出建议。

4

2 回答 2

2

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

  • 对于固定数量的数组（在 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加上由新集合的元素组成的单元素集合）。

于 2012-04-05T00:27:09.000 回答
0

根据 RBarryYoung 的提示，这是生成它们的最短方法 bash（和 sed，用于删除 D、w 和 4）：

echo {A..D}{w..z}{1..4} | sed 's/[Dw4]//g'

A1 A2 A3 A Ax1 Ax2 Ax3 Ax Ay1 Ay2 Ay3 Ay Az1 Az2 Az3 Az B1 B2 B3 B Bx1 Bx2 Bx3 Bx By1 By2 By3 By Bz1 Bz2 Bz3 Bz C1 C2 C3 C Cx1 Cx2 Cx3 Cx Cy1 Cy2 Cy3 Cy Cz1 Cz2 Cz3 Cz 1 2 3 x1 x2 x3 x y1 y2 y3 y z1 z2 z3 z

另一种简单的方法是 SQL，它默认执行此操作：

SELECT upper, lower, num 
FROM uppers, lowers, numbers
WHERE upper in ('A', 'B', 'C', ' ')
AND lower in (' ', 'x', 'y', 'z')
AND (number in (1, 2, 3) OR number IS NULL);

如果您的表格仅包含“A,B,C,,”和“x,y,z,,,”和“1,2,3”，则它要短得多：

SELECT upper, lower, num 
FROM uppers, lowers, numbers;

另一个词，除了笛卡尔积之外，这种组合是叉积。

对于未知数量的未知大小的列表/序列/其他集合，我会推荐一个迭代器——如果 PHP 有这样的东西。这是Scala中的一个实现：

  class CartesianIterator (val ll: Seq[Seq[_]]) extends Iterator [Seq[_]] {
    var current = 0
    def size = ll.map (_.size).product
    lazy val last: Int = len

    def get (n: Int, lili: Seq[Seq[_]]): List[_] = lili.length match {
      case 0 => List () 
      case _ => {
        val inner = lili.head 
        inner (n % inner.size) :: get (n / inner.size, lili.tail) 
      }
    }

    override def hasNext () : Boolean = current != last
    override def next (): Seq[_] = {
      current += 1
      get (current - 1, ll) 
    }
  }

  val ci = new CartesianIterator (List(List ('A', 'B', 'C', 'D', ' '), List ('x', 'y', 'z', ' '), List (1, 2, 3, 0)))
  for (c <- ci) println (c)

List(A, x, 1)
List(B, x, 1)
List(C, x, 1)
List(D, x, 1)
List( , x, 1)
List(A, y, 1)
List(B, y, 1)
...
List( , z, 0)
List(A,  , 0)
List(B,  , 0)
List(C,  , 0)
List(D,  , 0)
List( ,  , 0)

包装器可用于从输出中删除“0”和“”。

于 2012-04-05T01:32:39.090 回答