3

笔记

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

背景

REBOL语言支持创建特定领域的语言，在 REBOL用语中称为“方言” 。我为列表推导创建了这样一种方言，REBOL 本身并不支持这种方言。

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

问题

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

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

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

4

6 回答 6

6

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
]
于 2009-09-23T17:04:29.893 回答
5

像这样的东西怎么样：

#!/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
于 2008-10-19T03:18:12.337 回答
3

为了完整起见，以下是 Robert Gamble 翻译成 REBOL 的答案：

雷博尔[]

笛卡尔：函数[
    {给定一组集合，返回所述集合的笛卡尔积。}
    sets [block!] {一个包含一个或多个系列的块！价值观}
    /当地的
        元素
        结果
        排
][
    结果：复制 []

    元素：1
    foreach 集集 [
        elems：elems *（长度？设置）
    ]

    对于 n 0 (elems - 1) 1 [
        行：复制[]
        跳过：元素
        foreach 集集 [
            跳过：跳过/长度？放
            index: (mod to-integer (n / skip) length? set) + 1 ; REBOL 是从 1 开始的，而不是从 0 开始的
            追加行集/（索引）
        ]
        追加/仅结果行
    ]

    结果
]

foreach 设置笛卡尔 [[1 2] [3 4] [5 6]] [
    打印集
]

; 这将返回 Robert Gamble 的解决方案所做的相同的事情：

1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6
于 2008-10-20T13:34:17.413 回答
1 
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;
}

输出

1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6
于 2009-12-02T20:30:01.667 回答
1

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

在此示例中，列表“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);
        }
    }
}
于 2010-03-02T19:14:48.890 回答
0

编辑：这个解决方案不起作用。Robert Gamble's 是正确的解决方案。

我头脑风暴了一下，想出了这个解决方案：

（我知道你们中的大多数人不会知道 REBOL，但它是一种相当易读的语言。）

雷博尔[]

设置：[[1 2 3] [4 5] [6]] ；这是一组集合
元素：1
结果：复制 []
foreach 集合 [elems: elems * (length?set)]
对于 n 1 元素 1 [
    行：复制[]
    foreach 集集 [
        索引：1 + (mod (n - 1) 长度？设置)
        追加行集/（索引）
    ]
    追加/仅结果行
]

foreach 行结果 [
    打印结果
]

此代码产生：

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

（在第一次阅读上面的数字时，你可能会认为有重复。我做过。但没有。）

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

于 2008-10-19T10:15:27.923 回答