algorithm - デカルト積を計算するための優れた非再帰アルゴリズムは何ですか?

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

Answer 3

完全を期すために、REBOLに翻訳されたRobert Gambleの回答を次に示します。

リボル []

デカルト: func [
    {セットのブロックを指定すると、そのセットのデカルト積を返します。}
    [ブロック!] {1 つまたは複数のシリーズを含むブロック! 値}
    /ローカル
        要素
        結果
        行
][
    結果: [] をコピー

    要素: 1
    foreach セット セット [
        elems: elems * (長さ? セット)
    ]

    n 0 (要素 - 1) 1 [
        行: コピー []
        スキップ: 要素
        foreach セット セット [
            スキップ: スキップ/長さ? 設定
            index: (mod to-integer (n / skip) length? set) + 1 ; REBOL は 0 ベースではなく 1 ベースです
            行セット/(インデックス) を追加
        ]
        追加/結果行のみ
    ]

    結果
]

foreach set デカルト [[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

Answer 4

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

Answer 5

これは、任意の数の要素を持つ任意の数のセットのデカルト積を生成する 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);
        }
    }
}

Answer 6

編集：このソリューションは機能しません。RobertGamble'sが正しい解決策です。

私は少しブレインストーミングして、この解決策を思いつきました：

（私はあなたのほとんどがREBOLを知らないことを知っていますが、それはかなり読みやすい言語です。）

REBOL []

セット：[[1 2 3] [4 5] [6]]; これがセットのセットです
elems：1
結果：コピー[]
foreachセットセット[elems：elems *（length？set）]
n1要素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）を使用しています。