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

Note

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

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

Background

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.

REBOL语言支持在REBOL用语中创建称为“方言”的特定于域的语言。我为列表推导创建了这样的方言,这在REBOL中本身不受支持。

A good cartesian product algorithm is needed for list comprehensions.

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

The Problem

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.

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

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.)

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

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.

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

6 个解决方案

#1

How about something like this:

这样的事情怎么样:

#!/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:

其中产生以下输出:

#2

3 times Faster and less memory used (less recycles).

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
]

#3

For the sake of completeness, Here's Robert Gamble's answer translated into REBOL:

为了完整起见,这里的Robert Gamble的答案被翻译成REBOL:

REBOL []

cartesian: func [
    {Given a block of sets, returns the Cartesian product of said sets.}
    sets [block!] {A block containing one or more series! values}
    /local
        elems
        result
        row
][
    result: copy []

    elems: 1
    foreach set sets [
        elems: elems * (length? set)
    ]

    for n 0 (elems - 1) 1 [
        row: copy []
        skip: elems
        foreach set sets [
            skip: skip / length? set
            index: (mod to-integer (n / skip) length? set) + 1 ; REBOL is 1-based, not 0-based
            append row set/(index)
        ]
        append/only result row
    ]

    result
]

foreach set cartesian [[1 2] [3 4] [5 6]] [
    print set
]

; This returns the same thing Robert Gamble's solution did:

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

#4

Here is a Java code to generate Cartesian product for arbitrary number of sets with arbitrary number of elements.

这是一个Java代码,用于生成具有任意数量元素的任意数量的集合的笛卡尔积。

in this sample the list "ls" contains 4 sets (ls1,ls2,ls3 and ls4) as you can see "ls" can contain any number of sets with any number of elements.

在此示例中,列表“ls”包含4个集合(ls1,ls2,ls3和ls4),您可以看到“ls”可以包含任意数量的具有任意数量元素的集合。

import java.util.*;

public class CartesianProduct {

    private List <List <String>> ls = new ArrayList <List <String>> ();
    private List <String> ls1 = new ArrayList <String> ();
    private List <String> ls2 = new ArrayList <String> ();
    private List <String> ls3 = new ArrayList <String> ();
    private List <String> ls4 = new ArrayList <String> ();

    public List <String> generateCartesianProduct () {
        List <String> set1 = null;
        List <String> set2 = null;

        ls1.add ("a");
        ls1.add ("b");
        ls1.add ("c");

        ls2.add ("a2");
        ls2.add ("b2");
        ls2.add ("c2");

        ls3.add ("a3");
        ls3.add ("b3");
        ls3.add ("c3");
        ls3.add ("d3");

        ls4.add ("a4");
        ls4.add ("b4");

        ls.add (ls1);
        ls.add (ls2);
        ls.add (ls3);
        ls.add (ls4);

        boolean subsetAvailabe = true;
        int setCount = 0;

        try{    
            set1 = augmentSet (ls.get (setCount++), ls.get (setCount));
        } catch (IndexOutOfBoundsException ex) {
            if (set1 == null) {
                set1 = ls.get(0);
            }
            return set1;
        }

        do {
            try {
                setCount++;      
                set1 = augmentSet(set1,ls.get(setCount));
            } catch (IndexOutOfBoundsException ex) {
                subsetAvailabe = false;
            }
        } while (subsetAvailabe);
        return set1;
    }

    public List <String> augmentSet (List <String> set1, List <String> set2) {

        List <String> augmentedSet = new ArrayList <String> (set1.size () * set2.size ());
        for (String elem1 : set1) {
            for(String elem2 : set2) {
                augmentedSet.add (elem1 + "," + elem2);
            }
        }
        set1 = null; set2 = null;
        return augmentedSet;
    }

    public static void main (String [] arg) {
        CartesianProduct cp = new CartesianProduct ();
        List<String> cartesionProduct = cp.generateCartesianProduct ();
        for (String val : cartesionProduct) {
            System.out.println (val);
        }
    }
}

#5

use strict;

print "@$_\n" for getCartesian(
  [qw(1 2)],
  [qw(3 4)],
  [qw(5 6)],
);

sub getCartesian {
#
  my @input = @_;
  my @ret = map [$_], @{ shift @input };

  for my $a2 (@input) {
    @ret = map {
      my $v = $_;
      map [@$v, $_], @$a2;
    }
    @ret;
  }
  return @ret;
}

output

#6

EDIT: This solution doesn't work. Robert Gamble's is the correct solution.

编辑:此解决方案不起作用。 Robert Gamble是正确的解决方案。

I brainstormed a bit and came up with this solution:

我有点头脑风暴,想出了这个解决方案:

(I know most of you won't know REBOL, but it's a fairly readable language.)

(我知道大多数人都不会知道REBOL,但它是一种相当可读的语言。)

REBOL []

sets: [[1 2 3] [4 5] [6]] ; Here's a set of sets
elems: 1
result: copy []
foreach set sets [elems: elems * (length? set)]
for n 1 elems 1 [
    row: copy []
    foreach set sets [
        index: 1 + (mod (n - 1) length? set)
        append row set/(index)
    ]
    append/only result row
]

foreach row result [
    print result
]

This code produces:

此代码生成:

(Upon first reading the numbers above, you may think there are duplicates. I did. But there aren't.)

(首先阅读上面的数字,你可能认为有重复。我做了。但没有。)

Interestingly, this code uses almost the very same algorithm (1 + ((n - 1) % 9) that torpedoed my Digital Root question.

有趣的是,这段代码几乎使用了同样的算法(1 +((n - 1)%9)来破坏我的数字根问题。

#1