Qu'est-ce qu'un bon algorithme non récursif pour calculer un produit cartésien?

Question

Remarque

Ce n'est pas une question spécifique à REBOL. Vous pouvez y répondre dans n’importe quelle langue.

Arrière-plan

La langue REBOL prend en charge la création de langues propres à un domaine, appelées "dialectes". dans REBOL jargon . J'ai créé un tel dialecte pour les compréhensions de liste, qui ne sont pas supportées nativement dans REBOL.

Un bon algorithme de produit cartésien est nécessaire pour comprendre les listes.

Le problème

J'ai utilisé la méta-programmation pour résoudre ce problème, en créant de manière dynamique, puis en exécutant une séquence d'instructions foreach imbriquées. Cela fonctionne à merveille. Cependant, comme c'est dynamique, le code n'est pas très lisible. REBOL ne fait pas bien la récursivité. Il manque rapidement de pile et se bloque. Une solution récursive est donc hors de question.

En résumé, je souhaite remplacer ma méta-programmation par un "inline" lisible, non récursif. algorithme, si possible. La solution peut être dans n’importe quelle langue, à condition que je puisse la reproduire dans REBOL. (Je peux lire n'importe quel langage de programmation: C #, C, C ++, Perl, Oz, Haskell, Erlang, peu importe.)

Je dois souligner que cet algorithme doit prendre en charge un nombre arbitraire d'ensembles à "joindre", car la compréhension de liste peut impliquer un nombre quelconque d'ensembles.

Answer 1

Que diriez-vous de quelque chose comme ça:

#!/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 @
 Que diriez-vous de quelque chose comme ça: 

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


 Qui produit la sortie suivante: 

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

Qui produit la sortie suivante:

<*>

Answer 2

3 fois plus rapide et moins de mémoire utilisée (moins de recyclage).

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

Par souci d’exhaustivité, voici la réponse de Robert Gamble traduite en 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

Voici un code Java permettant de générer un produit cartésien pour un nombre arbitraire d'ensembles avec un nombre arbitraire d'éléments.

dans cet exemple, la liste " ls " contient 4 jeux (ls1, ls2, ls3 et ls4), comme vous pouvez le voir "ls" peut contenir un nombre quelconque d'ensembles contenant un nombre quelconque d'éléments.

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


 sortie 

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

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

 sortie 

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

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

 sortie 

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

 sortie 

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

sortie

<*>

Answer 6

MODIFIER: cette solution ne fonctionne pas. Robert Gamble est la solution correcte.

J'ai réfléchi un peu et suis venu avec cette solution:

(Je sais que la plupart d'entre vous ne connaîtront pas REBOL, mais c'est un langage assez lisible.)

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
]

Ce code produit:

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

(À la première lecture des chiffres ci-dessus, vous pouvez penser qu'il y a des doublons. C'est ce que j'ai fait. Mais il n'y en a pas.)

Fait intéressant, ce code utilise presque le même algorithme (1 + ((n - 1)% 9) qui a torpillé mon racine numérique .