Was ist ein guter, nicht-rekursive Algorithmus ein kartesisches Produkt zu berechnen?

Question

Hinweis

Dies ist keine REBOL spezifische Frage. Sie können es in jeder Sprache beantworten.

Hintergrund

Die REBOL Sprache unterstützt die Erstellung von domänenspezifischen Sprachen als "Dialekte" in REBOL bekannt parlance . Ich habe für Listenkomprehensionen einen solchen Dialekt erstellt, die nicht nativ in REBOL unterstützt.

Ein guter kartesisches Produkt Algorithmus für Listenkomprehensionen benötigt wird.

Das Problem

Ich habe verwendet Meta-Programmierung dieses Problem zu lösen, indem dynamisch erstellen und dann eine Folge von verschachtelten foreach Anweisungen ausgeführt werden. Es funktioniert wunderbar. Da es jedoch dynamisch ist, ist der Code nicht sehr gut lesbar. REBOL tut nicht gut Rekursion. Es läuft schnell aus Stapelspeicher und stürzt ab. So eine rekursive Lösung indiskutabel ist.

In der Summe mag ich meine Meta-Programmierung mit einem lesbaren, nicht-rekursive, „inline“ Algorithmus ersetzen, falls möglich. Die Lösung kann in jeder Sprache sein, solange ich es in REBOL wiedergeben kann. (Kann ich fast jede Programmiersprache lesen. C #, C, C ++, Perl, Oz, Haskell, Erlang, was auch immer)

Ich möchte betonen, dass dieser Algorithmus eine beliebige Anzahl von Sätzen unterstützen muss „verbunden“ werden, da Liste Verständnis eine beliebige Anzahl von Sätzen beinhalten kann.

Answer 1

Wie wäre es etwa so:

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

Welche erzeugt die folgende Ausgabe:

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-mal schneller und weniger Speicher verwendet (weniger recycles).

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

Aus Gründen der Vollständigkeit, hier Robert Gamble Antwort übersetzt 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

Answer 4

Hier ist ein Java-Code Kartesisches Produkt für beliebige Anzahl von Sätzen mit beliebiger Anzahl von Elementen zu erzeugen.

in diesem Beispiel die Liste „ls“ enthält vier Sätze (LS1, LS2, LS3 und LS4) wie Sie sehen können „ls“ eine beliebige Anzahl von Sätzen mit einer beliebigen Anzahl von Elementen enthalten.

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

Ausgang

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: Diese Lösung funktioniert nicht. Robert Gamble ist die richtige Lösung.

brainstormed ich ein wenig und kam mit dieser Lösung:

(Ich weiß, die meisten von Ihnen nicht REBOL wissen, aber es ist eine ziemlich lesbare Sprache.)

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
]

Dieser Code erzeugt:

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

(Auf den ersten, die Zahlen oben zu lesen, können Sie denken, es gibt Duplikate. Ich. Aber es gibt nicht).

Interessanterweise dieser Code verwendet fast den gleichen Algorithmus (1 + ((n - 1)% 9), die meine Digital-Root- Frage.