algorithm - que - dado los conjuntos

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

Question

Nota

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

Fondo

El lenguaje REBOL admite la creación de lenguajes específicos de dominio conocidos como "dialectos" en el lenguaje REBOL. Creé un dialecto para la comprensión de listas, que no se admite nativamente en REBOL.

Se necesita un buen algoritmo de producto cartesiano para la comprensión de la lista.

El problema

He usado la metaprogramación para resolver esto, creando dinámicamente y luego ejecutando una secuencia de enunciados foreach anidados. Funciona maravillosamente. 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 en la pila y se cuelga. Entonces una solución recursiva está fuera de discusión.

En resumen, quiero reemplazar mi meta-programación con un algoritmo legible, no recursivo, "en línea", 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 necesita admitir un número arbitrario de conjuntos para "unirse", ya que la comprensión de la lista puede involucrar cualquier cantidad 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 @$_ } @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:

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

En aras de la exhaustividad, 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 3

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 4

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

en esta muestra, la lista "ls" contiene 4 conjuntos (ls1, ls2, ls3 y ls4), como puede ver "ls" puede contener cualquier cantidad de conjuntos con cualquier cantidad 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;
}

salida

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

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

Discutí un poco y se me ocurrió esta solución:

(Sé que la mayoría de ustedes no sabrá 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, puede 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 pregunta de raíz digital .