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

一尘不染

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

algorithm

注意

这不是特定于REBOL的问题。您可以用任何语言回答。

背景

该REBOL语言支持被称为REBOL“方言”领域特定语言的创建说法
。我已经为列表解析创建了这样一种方言，REBOL本身不支持这种方言。

列表理解需要一个好的笛卡尔积算法。

问题

我使用元编程来解决此问题，方法是动态创建然后执行一系列嵌套foreach语句。它工作得很漂亮。但是，由于它是动态的，因此代码不太易读。REBOL的递归效果不佳。它迅速耗尽堆栈空间并崩溃。因此，递归解决方案是不可能的。

总而言之，如果可能的话，我想用可读的，非递归的“内联”算法替换元编程。该解决方案可以使用任何语言，只要我可以在REBOL中重现它即可。（我几乎可以阅读任何编程语言：C＃，C，C
++，Perl，Oz，Haskell，Erlang等。）

我应该强调，此算法需要支持任意数量的“连接”集，因为列表理解可以涉及任意数量的集。

阅读 268

2020-07-28

共1个答案

一尘不染

这样的事情怎么样：

#!/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;
}

产生以下输出：

2020-07-28