什么是一个很好的，非递归算法计算笛卡尔积？ [英] What's a good, non-recursive algorithm to calculate a Cartesian product?

问题描述

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

This is not a REBOL-specific question. You can answer it in any language.

借助 REBOL 语言支持创建在REBOL的被称为方言领域特定语言的说法的。我的列表COM prehensions，这本身不支持REBOL创造了这样一种方言。

The REBOL language supports the creation of domain-specific languages known as "dialects" in REBOL parlance. I've created such a dialect for list comprehensions, which aren't natively supported in REBOL.

一个很好的笛卡尔积算法是需要列表COM prehensions。

A good cartesian product algorithm is needed for list comprehensions.

我用的元编程来解决这个问题，通过动态创建，然后执行的嵌套的foreach 语句序列。它精美的作品。然而，因为它是动态的，code不是十分易读。 REBOL并不好做递归。它迅速耗尽堆栈空间和崩溃。因此，一个递归的解决方案是不可能的。

I've used meta-programming to solve this, by dynamically creating and then executing a sequence of nested foreach statements. It works beautifully. However, because it's dynamic, the code is not very readable. REBOL doesn't do recursion well. It rapidly runs out of stack space and crashes. So a recursive solution is out of the question.

总之，我想用一个可读的，非递归，内联的算法，来取代我的元编程如果可能的话。该解决方案可以在任何语言，只要我能在REBOL重现。 （我可以阅读几乎任何编程语言：C＃，C，C ++，Perl中，奥兹，哈斯克尔，二郎，等等）

In sum, I want to replace my meta-programming with a readable, non-recursive, "inline" algorithm, if possible. The solution can be in any language, as long as I can reproduce it in REBOL. (I can read just about any programming language: C#, C, C++, Perl, Oz, Haskell, Erlang, whatever.)

我要强调的是，这种算法需要支持的设置要加入任意数字，因为列表COM prehension可以涉及任何数量的集合。

I should stress that this algorithm needs to support an arbitrary number of sets to be "joined", since list comprehension can involve any number of sets.

推荐答案

怎么是这样的：

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

这将产生以下输出：

Which produces the following output:

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

这篇关于什么是一个很好的，非递归算法计算笛卡尔积？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！