데카르트 제품을 계산하기위한 좋은 비수체 알고리즘은 무엇입니까?
-
03-07-2019 - |
문제
메모
이것은 반군 별 질문이 아닙니다. 어떤 언어로든 대답 할 수 있습니다.
배경
그만큼 레볼 Language는 Rebol에서 "Dialects"로 알려진 도메인 별 언어의 생성을 지원합니다. 말투. 나는리스트 이해력을위한 그러한 방언을 만들었습니다.
목록 이해하려면 좋은 직교 제품 알고리즘이 필요합니다.
문제
메타 프로그래밍을 사용하여이를 해결 한 다음 중첩 시퀀스를 실행하여이를 해결했습니다. foreach
진술. 그것은 아름답게 작동합니다. 그러나 역동적이기 때문에 코드는 읽을 수 없습니다. 레볼은 재귀를 잘하지 않습니다. 스택 공간이 빠르게 떨어지고 충돌합니다. 따라서 재귀 솔루션은 의문의 여지가 없습니다.
요약하면, 나는 메타 프로그래밍을 가능한 경우 읽기 쉬운, 비수체 적 "인라인"알고리즘으로 바꾸고 싶습니다. 솔루션은 해상에서 재현 할 수있는 한 모든 언어로 될 수 있습니다. (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 @$_ } @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
다른 팁
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
]
완전성을 위해 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
다음은 임의의 요소가있는 임의의 세트에 대한 직교 제품을 생성하는 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 "@$_\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
편집하다: 이 솔루션은 작동하지 않습니다. Robert Gamble 's는 올바른 솔루션입니다.
나는 조금 브레인 스토밍 하고이 솔루션을 생각해 냈습니다.
(나는 대부분의 사람들이 데볼을 알지 못하지만 상당히 읽을 수있는 언어입니다.)
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
(위의 숫자를 처음 읽으면 중복이 있다고 생각할 수 있습니다.
흥미롭게 도이 코드는 거의 동일한 알고리즘 (1 + (N -1) % 9)을 사용하여 내 디지털 루트 의문.