¿Qué es un buen algoritmo no recursivo para calcular un producto cartesiano?

Question

Nota

Esta no es una pregunta específica de REBOL. Puedes responderla en cualquier idioma.

Fondo

El idioma REBOL admite la creación de lenguajes específicos de dominio conocidos como " dialects " " en REBOL parlance . He creado ese dialecto para las listas de comprensión, que no se admiten de forma nativa en REBOL.

Se necesita un buen algoritmo de producto cartesiano para comprender las listas.

El problema

He usado la meta-programación para resolver esto, creando dinámicamente y luego ejecutando una secuencia de declaraciones foreach anidadas. Funciona muy bien. Sin embargo, debido a que es dinámico, el código no es muy legible. REBOL no hace bien la recursión. Se queda rápidamente sin espacio de pila y se bloquea. Por lo tanto, una solución recursiva está fuera de discusión.

En resumen, quiero reemplazar mi meta-programación con una lectura legible, no recursiva, " en línea " Algoritmo, si es posible. La solución puede estar en cualquier idioma, siempre que pueda reproducirla en REBOL. (Puedo leer casi cualquier lenguaje de programación: C #, C, C ++, Perl, Oz, Haskell, Erlang, lo que sea).

Debo enfatizar que este algoritmo debe admitir un número arbitrario de conjuntos a unirse, ya que la comprensión de la lista puede incluir cualquier número de conjuntos.

Answer 1

¿Qué tal algo como esto?

#!/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 @
 ¿Qué tal algo como esto? 

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


 Que produce el siguiente resultado: 

<*> } @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 produce el siguiente resultado:

<*>

Answer 2

3 veces más rápido y menos memoria utilizada (menos reciclaje).

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

Para completar, aquí está la respuesta de Robert Gamble traducida a 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

Aquí hay un código Java para generar un producto cartesiano para un número arbitrario de conjuntos con un número arbitrario de elementos.

en este ejemplo, la lista " ls " contiene 4 conjuntos (ls1, ls2, ls3 y ls4) como puedes ver " ls " puede contener cualquier número de conjuntos con cualquier 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 "@
1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6


 salida 

<*>\n" for getCartesian(
  [qw(1 2)],
  [qw(3 4)],
  [qw(5 6)],
);

sub getCartesian {
#
  my @input = @_;
  my @ret = map [<*>

 salida 

<*>], @{ shift @input };

  for my $a2 (@input) {
    @ret = map {
      my $v = <*>

 salida 

<*>;
      map [@$v, <*>

 salida 

<*>], @$a2;
    }
    @ret;
  }
  return @ret;
}

salida

<*>

Answer 6

EDITAR: Esta solución no funciona. Robert Gamble es la solución correcta.

Cerebré un poco y encontré esta solución:

(Sé que la mayoría de ustedes no sabrán REBOL, pero es un lenguaje bastante legible)

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 produce:

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

(Al leer por primera vez los números anteriores, puedes pensar que hay duplicados. Lo hice. Pero no los hay).

Curiosamente, este código usa casi el mismo algoritmo (1 + ((n - 1)% 9) que torpedeó mi Raíz digital .