デカルト積を計算するための優れた非再帰アルゴリズムは何ですか?
https://stackoverflow.com/questions/215908
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
注記
これは REBOL 固有の質問ではありません。どの言語でも回答できます。
背景
の リボル 言語は、REBOL で「方言」として知られるドメイン固有の言語の作成をサポートします。 用語. 。REBOL ではネイティブにサポートされていないリスト内包表記用にこのような方言を作成しました。
リストの内包には、優れたデカルト積アルゴリズムが必要です。
問題
私はメタプログラミングを使用して、ネストされたシーケンスを動的に作成して実行することで、これを解決しました。 foreach 発言。美しく機能します。ただし、動的であるため、コードはあまり読みにくくなります。REBOL は再帰がうまく機能しません。すぐにスタック領域が不足し、クラッシュします。したがって、再帰的な解決策は問題外です。
要約すると、可能であれば、メタプログラミングを読み取り可能な非再帰的な「インライン」アルゴリズムに置き換えたいと考えています。REBOL で再現できる限り、解決策はどの言語でも可能です。(私はほぼすべてのプログラミング言語を読むことができます。C#、C、C++、Perl、Oz、Haskell、Erlang など)。
リストの内包には任意の数のセットが含まれる可能性があるため、このアルゴリズムは「結合」される任意の数のセットをサポートする必要があることを強調しておきます。
解決
このようなものはどうですか：
#!/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 @このようなものはどうですか：
1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6
次の出力が生成されます：
<*> } @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;
}
次の出力が生成されます：
<*>他のヒント
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
]
完全を期すために、REBOLに翻訳されたRobert Gambleの回答を以下に示します。
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
以下は、任意の数の要素を持つ任意の数のセットのデカルト積を生成する 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);
}
}
}
use strict;
print "@1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6
出力
<*>\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;
}
出力
<*>編集：このソリューションは機能しません。 Robert Gamble'sが正しいソリューションです。
少しブレインストーミングして、この解決策を思いつきました：
（ほとんどの人が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
]
このコードは以下を生成します：
1 4 6
2 5 6
3 4 6
1 5 6
2 4 6
3 5 6
（最初に上記の数字を読んだとき、重複していると思うかもしれません。私はしました。しかしありません。）
興味深いことに、このコードは私のデジタルルートの質問。
