Prodotto cartesiano iterativo in Java

Question

Voglio calcolare il prodotto cartesiano di un numero arbitrario di set di caratteri non vuoti in Java.

ho scritto che il codice iterativo ...

public static <T> List<Set<T>> cartesianProduct(List<Set<T>> list) { 
    List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size()); 
    List<T> elements = new ArrayList<T>(list.size()); 
    List<Set<T>> toRet = new ArrayList<Set<T>>(); 
    for (int i = 0; i < list.size(); i++) { 
     iterators.add(list.get(i).iterator()); 
     elements.add(iterators.get(i).next()); 
    } 
    for (int j = 1; j >= 0;) { 
     toRet.add(Sets.newHashSet(elements)); 
     for (j = iterators.size()-1; j >= 0 && !iterators.get(j).hasNext(); j--) { 
      iterators.set(j, list.get(j).iterator()); 
      elements.set(j, iterators.get(j).next()); 
     } 
     elements.set(Math.abs(j), iterators.get(Math.abs(j)).next()); 
    } 
    return toRet; 
} 

... ma ho trovato piuttosto poco elegante. Qualcuno ha una migliore soluzione ancora iterativo? Una soluzione che utilizza un meraviglioso approccio di tipo funzionale? Altrimenti ... suggerimento su come migliorarlo? Errori?

Answer 1

Ho scritto una soluzione che non richiede di riempire una grande collezione in memoria. Sfortunatamente, il codice richiesto è lungo centinaia di righe. Potrebbe essere necessario attendere che compaia nel progetto Guava (http://guava-libraries.googlecode.com), che spero sarà entro la fine dell'anno. Scusate. :(

Notare che non potrebbe essere necessario un programma di utilità, se il numero di set sei cartesiano-produttrici è un numero fisso noto in fase di compilazione -. Si potrebbe utilizzare lo stesso numero di cicli for innestati

MODIFICA: il codice è ora disponibile.

Sets.cartesianProduct()

penso che sarai molto felice con lui. Crea solo le liste individuali come le chiedi; non riempie la memoria con tutti i MxNxPxQ di loro.

Se si desidera controllare la fonte, è here at line 727.

Divertiti!

Answer 2

potreste essere interessati a Un'altra domanda sui prodotti cartesiani (edit: rimossi per conservare i collegamenti ipertestuali, cercare il tag prodotti cartesiani). Quella risposta ha una bella soluzione ricorsiva che avrei difficoltà a migliorare. Vuoi in particolare una soluzione iterativa invece di una soluzione ricorsiva?

---

EDIT:

Dopo aver guardato un'altra soluzione iterativa su stack overflow in perl e a clean explanation, qui è un'altra soluzione:

public static <T> List<Set<T>> uglyCartesianProduct(List<Set<T>> list) { 
     List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size()); 
     List<T> elements = new ArrayList<T>(list.size()); 
     List<Set<T>> toRet = new ArrayList<Set<T>>(); 

     for (int i = 0; i < list.size(); i++) { 
      iterators.add(list.get(i).iterator()); 
      elements.add(iterators.get(i).next()); 
     } 

     for(int i = 0; i < numberOfTuples(list); i++) 
     { 
      toRet.add(new HashSet<T>()); 
     } 

     int setIndex = 0; 
     for (Set<T> set : list) { 
      int index = 0; 
      for (int i = 0; i < numberOfTuples(list); i++) { 
       toRet.get(index).add((T) set.toArray()[index % set.size()]); 
       index++; 
      } 
      setIndex++; 
     } 

     return toRet; 
    } 

    private static <T> int numberOfTuples(List<Set<T>> list) { 
     int product = 1; 
     for (Set<T> set : list) { 
      product *= set.size(); 
     } 
     return product; 
    } 

Answer 3

Credo che questo sia corretto. Non cerca l'efficienza, ma uno stile pulito attraverso la ricorsione e l'astrazione.

L'astrazione chiave è quello di introdurre una semplice classe Tuple. Questo aiuta i farmaci generici in seguito:

class Tuple<T> { 
    private List<T> list = new ArrayList<T>(); 

    public void add(T t) { list.add(t); } 

    public void addAll(Tuple<T> subT) { 
     for (T t : subT.list) { 
      list.add(t); 
     } 
    } 

    public String toString() { 
     String result = "("; 

     for (T t : list) { result += t + ", "; } 

     result = result.substring(0, result.length() - 2); 
     result += ")"; 

     return result; 
    } 
} 

Con questa classe, possiamo scrivere una classe in questo modo:

public class Example { 

public static <T> List<Tuple<T>> cartesianProduct(List<Set<T>> sets) { 
    List<Tuple<T>> tuples = new ArrayList<Tuple<T>>(); 

    if (sets.size() == 1) { 
     Set<T> set = sets.get(0); 
     for (T t : set) { 
      Tuple<T> tuple = new Tuple<T>(); 
      tuple.add(t);  
      tuples.add(tuple); 
     } 
    } else { 
     Set<T> set = sets.remove(0); 
     List<Tuple<T>> subTuples = cartesianProduct(sets); 
     System.out.println("TRACER size = " + tuples.size()); 
     for (Tuple<T> subTuple : subTuples) { 
      for (T t : set) { 
       Tuple<T> tuple = new Tuple<T>(); 
       tuple.addAll(subTuple); 
       tuple.add(t); 
       tuples.add(tuple); 
      } 
     } 
    } 

    return tuples; 
} 

}

Ho un esempio decente di questo lavoro, ma viene omesso per brevità.

Answer 4

La risposta seguente utilizza l'iterazione e non ricorsione. Esso utilizza la stessa Tuple classe da mia risposta precedente.

È una risposta separata perché entrambi sono validi, approcci diversi.

Ecco la nuova classe principale:

public class Example { 

    public static <T> List<Tuple<T>> cartesianProduct(List<Set<T>> sets) { 
     List<Tuple<T>> tuples = new ArrayList<Tuple<T>>(); 

     for (Set<T> set : sets) {    
      if (tuples.isEmpty()) { 
       for (T t : set) { 
        Tuple<T> tuple = new Tuple<T>(); 
        tuple.add(t);  
        tuples.add(tuple); 
       }     
      } else { 
       List<Tuple<T>> newTuples = new ArrayList<Tuple<T>>(); 

       for (Tuple<T> subTuple : tuples) { 
        for (T t : set) { 
         Tuple<T> tuple = new Tuple<T>(); 
         tuple.addAll(subTuple); 
         tuple.add(t); 
         newTuples.add(tuple); 
        } 
       }     

       tuples = newTuples; 
      } 
     } 

     return tuples; 
    } 
} 

Answer 5

Ecco un approccio di iteratore pigro che utilizza una funzione per produrre un tipo di output appropriato.

public static <T> Iterable<T> cartesianProduct(
     final Function<Object[], T> fn, Object[]... options) { 
    final Object[][] opts = new Object[options.length][]; 
    for (int i = opts.length; --i >= 0;) { 
     // NPE on null input collections, and handle the empty output case here 
     // since the iterator code below assumes that it is not exhausted the 
     // first time through fetch. 
     if (options[i].length == 0) { return Collections.emptySet(); } 
     opts[i] = options[i].clone(); 
    } 
    return new Iterable<T>() { 
     public Iterator<T> iterator() { 
     return new Iterator<T>() { 
      final int[] pos = new int[opts.length]; 
      boolean hasPending; 
      T pending; 
      boolean exhausted; 

      public boolean hasNext() { 
      fetch(); 
      return hasPending; 
      } 

      public T next() { 
      fetch(); 
      if (!hasPending) { throw new NoSuchElementException(); } 
      T out = pending; 
      pending = null; // release for GC 
      hasPending = false; 
      return out; 
      } 

      public void remove() { throw new UnsupportedOperationException(); } 

      private void fetch() { 
      if (hasPending || exhausted) { return; } 
      // Produce a result. 
      int n = pos.length; 
      Object[] args = new Object[n]; 
      for (int j = n; --j >= 0;) { args[j] = opts[j][pos[j]]; } 
      pending = fn.apply(args); 
      hasPending = true; 
      // Increment to next. 
      for (int i = n; --i >= 0;) { 
       if (++pos[i] < opts[i].length) { 
       for (int j = n; --j > i;) { pos[j] = 0; } 
       return; 
       } 
      } 
      exhausted = true; 
      } 
     }; 
     } 
    }; 
    } 

Answer 6

ho scritto un algoritmo ricorsivo prodotto cartesiano per la tabella di stringhe. Puoi modificarlo per impostare gli insiemi. Di seguito è riportato l'algoritmo. E 'anche spiegato nel mio article

public class Main { 

public static void main(String[] args) { 
    String[] A = new String[]{ "a1", "a2", "a3" }; 
    String[] B = new String[]{ "b1", "b2", "b3" }; 
    String[] C = new String[]{ "c1" }; 

    String[] cp = CartesianProduct(0, A, B, C); 

    for(String s : cp) { 
     System.out.println(s); 
    } 
} 

public static String[] CartesianProduct(int prodLevel, String[] res, String[] ...s) { 
    if(prodLevel < s.length) { 
     int cProdLen = res.length * s[prodLevel].length; 
     String[] tmpRes = new String[cProdLen]; 

     for (int i = 0; i < res.length; i++) { 
      for (int j = 0; j < s[prodLevel].length; j++) { 
       tmpRes[i * res.length + j] = res[i] + s[prodLevel][j]; 
      } 
     } 
     res = Main.CartesianProduct(prodLevel + 1, tmpRes, s); 
    } 
    return res; 
}} 

Answer 7

Ecco un iterativo, pigro implementazione ho scritto. L'interfaccia è molto simile a Sets.cartesianProduct di Google, ma è un po 'più flessibile: tratta in Iterables invece di Sets. Questo codice e i suoi test unitari sono disponibili al https://gist.github.com/1911614.

/* Copyright 2012 LinkedIn Corp. 

    Licensed under the Apache License, Version 2.0 (the "License"); 
    you may not use this file except in compliance with the License. 
    You may obtain a copy of the License at 

     http://www.apache.org/licenses/LICENSE-2.0 

    Unless required by applicable law or agreed to in writing, software 
    distributed under the License is distributed on an "AS IS" BASIS, 
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
    See the License for the specific language governing permissions and 
    limitations under the License. 
*/ 

import com.google.common.base.Function; 
import com.google.common.collect.Iterables; 
import java.lang.reflect.Array; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 
import java.util.Iterator; 
import java.util.List; 
import java.util.NoSuchElementException; 

/** 
* Implements the Cartesian product of ordered collections. 
* 
* @author <a href="mailto:jmkristian@gmail.com">John Kristian</a> 
*/ 
public class Cartesian { 
    /** 
    * Generate the <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 
    * product</a> of the given axes. For axes [[a1, a2 ...], [b1, b2 ...], [c1, c2 ...] 
    * ...] the product is [[a1, b1, c1 ...] ... [a1, b1, c2 ...] ... [a1, b2, c1 ...] ... 
    * [aN, bN, cN ...]]. In other words, the results are generated in same order as these 
    * nested loops: 
    * 
    * <pre> 
    * for (T a : [a1, a2 ...]) 
    * for (T b : [b1, b2 ...]) 
    *  for (T c : [c1, c2 ...]) 
    *  ... 
    *   result = new T[]{ a, b, c ... }; 
    * </pre> 
    * 
    * Each result is a new array of T, whose elements refer to the elements of the axes. If 
    * you prefer a List, you can call asLists(product(axes)). 
    * <p> 
    * Don't change the axes while iterating over their product, as a rule. Changes to an 
    * axis can affect the product or cause iteration to fail (which is usually bad). To 
    * prevent this, you can pass clones of your axes to this method. 
    * <p> 
    * The implementation is lazy. This method iterates over the axes, and returns an 
    * Iterable that contains a reference to each axis. Iterating over the product causes 
    * iteration over each axis. Methods of each axis are called as late as practical. 
    */ 
    public static <T> Iterable<T[]> product(Class<T> resultType, 
              Iterable<? extends Iterable<? extends T>> axes) { 
    return new Product<T>(resultType, newArray(Iterable.class, axes)); 
    } 

    /** Works like product(resultType, Arrays.asList(axes)), but slightly more efficient. */ 
    public static <T> Iterable<T[]> product(Class<T> resultType, Iterable<? extends T>... axes) { 
    return new Product<T>(resultType, axes.clone()); 
    } 

    /** 
    * Wrap the given arrays in fixed-size lists. Changes to the lists write through to the 
    * arrays. 
    */ 
    public static <T> Iterable<List<T>> asLists(Iterable<? extends T[]> arrays) { 
    return Iterables.transform(arrays, new AsList<T>()); 
    } 

    /** 
    * Arrays.asList, represented as a Function (as used in Google collections). 
    */ 
    public static class AsList<T> implements Function<T[], List<T>> { 
    @Override 
    public List<T> apply(T[] array) { 
     return Arrays.asList(array); 
    } 
    } 

    /** Create a generic array containing references to the given objects. */ 
    private static <T> T[] newArray(Class<? super T> elementType, Iterable<? extends T> from) { 
    List<T> list = new ArrayList<T>(); 
    for (T f : from) 
     list.add(f); 
    return list.toArray(newArray(elementType, list.size())); 
    } 

    /** Create a generic array. */ 
    @SuppressWarnings("unchecked") 
    private static <T> T[] newArray(Class<? super T> elementType, int length) { 
    return (T[]) Array.newInstance(elementType, length); 
    } 

    private static class Product<T> implements Iterable<T[]> { 
    private final Class<T> _resultType; 
    private final Iterable<? extends T>[] _axes; 

    /** Caution: the given array of axes is contained by reference, not cloned. */ 
    Product(Class<T> resultType, Iterable<? extends T>[] axes) { 
     _resultType = resultType; 
     _axes = axes; 
    } 

    @Override 
    public Iterator<T[]> iterator() { 
     if (_axes.length <= 0) // an edge case 
     return Collections.singleton(newArray(_resultType, 0)).iterator(); 
     return new ProductIterator<T>(_resultType, _axes); 
    } 

    @Override 
    public String toString() { 
     return "Cartesian.product(" + Arrays.toString(_axes) + ")"; 
    } 

    private static class ProductIterator<T> implements Iterator<T[]> { 
     private final Iterable<? extends T>[] _axes; 
     private final Iterator<? extends T>[] _iterators; // one per axis 
     private final T[] _result; // a copy of the last result 
     /** 
     * The minimum index such that this.next() will return an array that contains 
     * _iterators[index].next(). There are some special sentinel values: NEW means this 
     * is a freshly constructed iterator, DONE means all combinations have been 
     * exhausted (so this.hasNext() == false) and _iterators.length means the value is 
     * unknown (to be determined by this.hasNext). 
     */ 
     private int _nextIndex = NEW; 
     private static final int NEW = -2; 
     private static final int DONE = -1; 

     /** Caution: the given array of axes is contained by reference, not cloned. */ 
     ProductIterator(Class<T> resultType, Iterable<? extends T>[] axes) { 
     _axes = axes; 
     _iterators = Cartesian.<Iterator<? extends T>> newArray(Iterator.class, _axes.length); 
     for (int a = 0; a < _axes.length; ++a) { 
      _iterators[a] = axes[a].iterator(); 
     } 
     _result = newArray(resultType, _iterators.length); 
     } 

     private void close() { 
     _nextIndex = DONE; 
     // Release references, to encourage garbage collection: 
     Arrays.fill(_iterators, null); 
     Arrays.fill(_result, null); 
     } 

     @Override 
     public boolean hasNext() { 
     if (_nextIndex == NEW) { // This is the first call to hasNext(). 
      _nextIndex = 0; // start here 
      for (Iterator<? extends T> iter : _iterators) { 
      if (!iter.hasNext()) { 
       close(); // no combinations 
       break; 
      } 
      } 
     } else if (_nextIndex >= _iterators.length) { 
      // This is the first call to hasNext() after next() returned a result. 
      // Determine the _nextIndex to be used by next(): 
      for (_nextIndex = _iterators.length - 1; _nextIndex >= 0; --_nextIndex) { 
      Iterator<? extends T> iter = _iterators[_nextIndex]; 
      if (iter.hasNext()) { 
       break; // start here 
      } 
      if (_nextIndex == 0) { // All combinations have been generated. 
       close(); 
       break; 
      } 
      // Repeat this axis, with the next value from the previous axis. 
      iter = _axes[_nextIndex].iterator(); 
      _iterators[_nextIndex] = iter; 
      if (!iter.hasNext()) { // Oops; this axis can't be repeated. 
       close(); // no more combinations 
       break; 
      } 
      } 
     } 
     return _nextIndex >= 0; 
     } 

     @Override 
     public T[] next() { 
     if (!hasNext()) 
      throw new NoSuchElementException("!hasNext"); 
     for (; _nextIndex < _iterators.length; ++_nextIndex) { 
      _result[_nextIndex] = _iterators[_nextIndex].next(); 
     } 
     return _result.clone(); 
     } 

     @Override 
     public void remove() { 
     for (Iterator<? extends T> iter : _iterators) { 
      iter.remove(); 
     } 
     } 

     @Override 
     public String toString() { 
     return "Cartesian.product(" + Arrays.toString(_axes) + ").iterator()"; 
     } 
    } 
    } 
} 

Answer 8

N-based soluzione

Lavorare con gli indici è una semplice alternativa che è veloce e la memoria efficiente e può gestire qualsiasi numero di gruppi. L'implementazione di Iterable consente un facile utilizzo in un ciclo for-each. Vedi il metodo #main per un esempio di utilizzo.

public class CartesianProduct implements Iterable<int[]>, Iterator<int[]> { 

private final int[] _lengths; 
private final int[] _indices; 
private boolean _hasNext = true; 

public CartesianProduct(int[] lengths) { 
    _lengths = lengths; 
    _indices = new int[lengths.length]; 
} 

public boolean hasNext() { 
    return _hasNext; 
} 

public int[] next() { 
    int[] result = Arrays.copyOf(_indices, _indices.length); 
    for (int i = _indices.length - 1; i >= 0; i--) { 
     if (_indices[i] == _lengths[i] - 1) { 
      _indices[i] = 0; 
      if (i == 0) { 
       _hasNext = false; 
      } 
     } else { 
      _indices[i]++; 
      break; 
     } 
    } 
    return result; 
} 

public Iterator<int[]> iterator() { 
    return this; 
} 

public void remove() { 
    throw new UnsupportedOperationException(); 
} 

/** 
* Usage example. Prints out 
* 
* <pre> 
* [0, 0, 0] a, NANOSECONDS, 1 
* [0, 0, 1] a, NANOSECONDS, 2 
* [0, 0, 2] a, NANOSECONDS, 3 
* [0, 0, 3] a, NANOSECONDS, 4 
* [0, 1, 0] a, MICROSECONDS, 1 
* [0, 1, 1] a, MICROSECONDS, 2 
* [0, 1, 2] a, MICROSECONDS, 3 
* [0, 1, 3] a, MICROSECONDS, 4 
* [0, 2, 0] a, MILLISECONDS, 1 
* [0, 2, 1] a, MILLISECONDS, 2 
* [0, 2, 2] a, MILLISECONDS, 3 
* [0, 2, 3] a, MILLISECONDS, 4 
* [0, 3, 0] a, SECONDS, 1 
* [0, 3, 1] a, SECONDS, 2 
* [0, 3, 2] a, SECONDS, 3 
* [0, 3, 3] a, SECONDS, 4 
* [0, 4, 0] a, MINUTES, 1 
* [0, 4, 1] a, MINUTES, 2 
* ... 
* </pre> 
*/ 
public static void main(String[] args) { 
    String[] list1 = { "a", "b", "c", }; 
    TimeUnit[] list2 = TimeUnit.values(); 
    int[] list3 = new int[] { 1, 2, 3, 4 }; 

    int[] lengths = new int[] { list1.length, list2.length, list3.length }; 
    for (int[] indices : new CartesianProduct(lengths)) { 
     System.out.println(Arrays.toString(indices) // 
       + " " + list1[indices[0]] // 
       + ", " + list2[indices[1]] // 
       + ", " + list3[indices[2]]); 
    } 
} 

}

Answer 9

Utilizzando Google Guava 19 e Java 8 è molto semplice:

Diciamo che avete l'elenco di tutti gli array che si desidera associare ...

public static void main(String[] args) { 
    List<String[]> elements = Arrays.asList(
    new String[]{"John", "Mary"}, 
    new String[]{"Eats", "Works", "Plays"}, 
    new String[]{"Food", "Computer", "Guitar"} 
); 

    // Create a list of immutableLists of strings 
    List<ImmutableList<String>> immutableElements = makeListofImmutable(elements); 

    // Use Guava's Lists.cartesianProduct, since Guava 19 
    List<List<String>> cartesianProduct = Lists.cartesianProduct(immutableElements); 

    System.out.println(cartesianProduct); 
} 

Il metodo per rendere l'elenco di elenchi immutabili è il seguente:

/** 
* @param values the list of all profiles provided by the client in matrix.json 
* @return the list of ImmutableList to compute the Cartesian product of values 
*/ 
private static List<ImmutableList<String>> makeListofImmutable(List<String[]> values) { 
    List<ImmutableList<String>> converted = new LinkedList<>(); 
    values.forEach(array -> { 
    converted.add(ImmutableList.copyOf(array)); 
    }); 
    return converted; 
} 

L'uscita è la seguente:

[ 
    [John, Eats, Food], [John, Eats, Computer], [John, Eats, Guitar], 
    [John, Works, Food], [John, Works, Computer], [John, Works, Guitar], 
    [John, Plays, Food], [John, Plays, Computer], [John, Plays, Guitar], 
    [Mary, Eats, Food], [Mary, Eats, Computer], [Mary, Eats, Guitar], 
    [Mary, Works, Food], [Mary, Works, Computer], [Mary, Works, Guitar], 
    [Mary, Plays, Food], [Mary, Plays, Computer], [Mary, Plays, Guitar] 
]