Che cos'è un buon algoritmo non ricorsivo per calcolare un prodotto cartesiano?
-
03-07-2019 - |
Domanda
Nota ??h3>
Questa non è una domanda specifica di REBOL. Puoi rispondere in qualsiasi lingua.
Sfondo
La REBOL supporta la creazione di lingue specifiche del dominio note come " dialetti " in REBOL parlance . Ho creato un dialetto simile per la comprensione delle liste, che non sono supportate nativamente in REBOL.
È necessario un buon algoritmo cartesiano per la comprensione dell'elenco.
Il problema
Ho usato la meta-programmazione per risolvere questo problema, creando dinamicamente e quindi eseguendo una sequenza di istruzioni nidificate foreach
. Funziona magnificamente. Tuttavia, poiché è dinamico, il codice non è molto leggibile. REBOL non fa bene la ricorsione. Si esaurisce rapidamente nello spazio dello stack e si arresta in modo anomalo. Quindi una soluzione ricorsiva è fuori discussione.
In breve, voglio sostituire la mia meta-programmazione con una lettura, non ricorsiva, "inline" algoritmo, se possibile. La soluzione può essere in qualsiasi lingua, purché sia ??possibile riprodurla in REBOL. (Posso leggere praticamente qualsiasi linguaggio di programmazione: C #, C, C ++, Perl, Oz, Haskell, Erlang, qualunque cosa.)
Dovrei sottolineare che questo algoritmo deve supportare un numero arbitrario di set per essere "unito", poiché la comprensione dell'elenco può comportare un numero qualsiasi di set.
Soluzione
Che ne dici di qualcosa del genere:
#!/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 @ Che ne dici di qualcosa del genere:
1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6
Che produce il seguente output:
<*> } @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;
}
Che produce il seguente output:
<*>Altri suggerimenti
3 volte più veloce e meno memoria utilizzata (meno ricicla).
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
]
Per completezza, ecco la risposta di Robert Gamble tradotta in 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
Ecco un codice Java per generare un prodotto cartesiano per un numero arbitrario di set con un numero arbitrario di elementi.
in questo esempio la lista "ls" contiene 4 set (ls1, ls2, ls3 e ls4) come puoi vedere " ls " può contenere qualsiasi numero di set con qualsiasi numero di elementi.
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
uscita ??p>
<*>\n" for getCartesian(
[qw(1 2)],
[qw(3 4)],
[qw(5 6)],
);
sub getCartesian {
#
my @input = @_;
my @ret = map [<*>
uscita ??p>
<*>], @{ shift @input };
for my $a2 (@input) {
@ret = map {
my $v = <*>
uscita ??p>
<*>;
map [@$v, <*>
uscita ??p>
<*>], @$a2;
}
@ret;
}
return @ret;
}
uscita ??p> <*>
MODIFICA: questa soluzione non funziona. Robert Gamble è la soluzione corretta.
Ho fatto un po 'di brainstorming e ho trovato questa soluzione:
(So che molti di voi non conosceranno REBOL, ma è un linguaggio abbastanza leggibile.)
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 ]
Questo codice produce:
1 4 6
2 5 6
3 4 6
1 5 6
2 4 6
3 5 6
(Dopo aver letto i numeri sopra, potresti pensare che ci siano duplicati. L'ho fatto. Ma non ci sono.)
È interessante notare che questo codice utilizza quasi lo stesso algoritmo (1 + ((n - 1)% 9) che ha silurato il mio Radice digitale domanda.