O que é uma boa, o algoritmo não-recursivo para calcular um produto cartesiano?

Question

Nota

Esta não é uma questão específica de REBOL. Você pode responder em qualquer idioma.

Fundo

O REBOL suportes de linguagem a criação de linguagens específicas de domínio conhecidos como "dialetos" em REBOL jargão . Eu criei um tal dialeto compreensões lista, que não são suportados nativamente no REBOL.

Um bom algoritmo produto cartesiano é necessário para compreensões lista.

O Problema

Eu usei-meta programação para resolver isso, criando de forma dinâmica e, em seguida, executar uma sequência de declarações foreach aninhadas. Ele funciona muito bem. No entanto, porque é dinâmico, o código não é muito legível. não REBOL não fazem bem a recursividade. Corre-se rapidamente para fora do espaço de pilha e falhas. Assim, uma solução recursiva é fora de questão.

Em suma, eu quero substituir o meu meta-programação com um não-recursivo, algoritmo legível, "inline", se possível. A solução pode estar em qualquer idioma, desde que eu possa reproduzi-lo em REBOL. (I pode ler praticamente qualquer linguagem de programação:. C #, C, C ++, Perl, Oz, Haskell, Erlang, qualquer que seja)

Gostaria de salientar que este algoritmo necessidades para suportar um número arbitrário de conjuntos de ser "unidas", uma vez compreensão da lista pode envolver qualquer número de sets.

Answer 1

Como sobre algo como isto:

#!/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;
}

Que produz o seguinte resultado:

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 2

3 vezes mais rápido e menos memória usada (menos recicla).

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 3

Por uma questão de exaustividade, aqui está a resposta de Robert Gamble traduzido em 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

Answer 4

Aqui está um código Java para gerar produto cartesiano para número arbitrário de conjuntos com número arbitrário de elementos.

nesta amostra lista "ls" contém 4 conjuntos (ls1, LS2, LS3 e LS4) como você pode ver "ls" pode conter qualquer número de conjuntos com qualquer número de elementos.

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 5

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;
}

saída

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 6

EDIT: Esta solução não funciona. Robert Gamble é a solução correta.

Eu brainstormed um pouco e veio com esta solução:

(Eu sei que a maioria de vocês não vai saber REBOL, mas é uma linguagem bastante legível.)

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
]

Este código produz:

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

(Após a primeira leitura dos números acima, você pode pensar que não são duplicados. Eu fiz. Mas não há.)

Curiosamente, este usa o código quase o mesmo algoritmo (1 + ((n - 1)% 9) que torpedeado meu questão Root digital .