什么是计算笛卡尔积的好的非递归算法？

Question

注意

这不是REBOL特定的问题.你可以用任何语言回答它.

背景

该REBOL语言支持被称为REBOL"方言"领域特定语言的创建说法.我为列表推导创建了这样一种方言,REBOL本身不支持这种方言.

列表推导需要一个好的笛卡尔积算法.

问题

我已经使用元编程来解决这个问题,通过动态创建然后执行一系列嵌套foreach语句.它工作得很漂亮.但是,因为它是动态的,所以代码不是很易读.REBOL不能很好地进行递归.它迅速耗尽堆栈空间和崩溃.因此,递归解决方案是不可能的.

总之,如果可能的话,我想用可读的,非递归的"内联"算法替换我的元编程.解决方案可以使用任何语言,只要我可以在REBOL中重现它.(我可以阅读任何编程语言:C#,C,C++,Perl,Oz,Haskell,Erlang等等.)

我应该强调,这个算法需要支持任意数量的集合才能"加入",因为列表理解可能涉及任意数量的集合.

Answer 1

3倍更快,使用的内存更少(回收更少).

cartesian: func [
 d [block! ] 
 /local len set i res

][
 d: copy d
 len: 1
 res: make block! foreach d d [len: len * length? d]
 len: length? d
 until [
  set: clear []
  loop i: len [insert set d/:i/1   i: i - 1]
  res: change/only res copy set
  loop i: len [
   unless tail? d/:i: next d/:i [break]
   if i = 1 [break]
   d/:i: head d/:i
   i: i - 1
  ]
  tail? d/1
 ]
 head res
]

Answer 2

这样的事情怎么样:

#!/usr/bin/perl

use strict;
use warnings;

my @list1 = qw(1 2);
my @list2 = qw(3 4);
my @list3 = qw(5 6);

# Calculate the Cartesian Product
my @cp = cart_prod(\@list1, \@list2, \@list3);

# Print the result
foreach my $elem (@cp) {
  print join(' ', @$elem), "\n";
}

sub cart_prod {
  my @sets = @_;
  my @result;
  my $result_elems = 1;

  # Calculate the number of elements needed in the result
  map { $result_elems *= scalar @$_ } @sets;
  return undef if $result_elems == 0;

  # Go through each set and add the appropriate element
  # to each element of the result
  my $scale_factor = $result_elems;
  foreach my $set (@sets)
  {
    my $set_elems = scalar @$set;  # Elements in this set
    $scale_factor /= $set_elems;
    foreach my $i (0 .. $result_elems - 1) {
      # Calculate the set element to place in this position
      # of the result set.
      my $pos = $i / $scale_factor % $set_elems;
      push @{$result[$i]}, $$set[ $pos ];
    }
  }

  return @result;
}

其中产生以下输出:

1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6