Повторяющееся декартово произведение в Java

В следующем ответе используется итерация, а не рекурсия. Он использует тот же класс Tuple из моего предыдущего ответа.

Это отдельный ответ, потому что, IMHO, оба действительны, разные подходы.

Вот новый основной класс:

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

Я считаю, что это правильно. Это не стремление к эффективности, а чистый стиль посредством рекурсии и абстракции.

Ключевой абстракцией является введение простого класса Tuple . Это поможет дженерикам позже:

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

С помощью этого класса мы можем написать такой класс:

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

}

У меня есть достойный пример такой работы, но он опущен для краткости.

Возможно, вас заинтересует Другой вопрос о декартовых произведениях (редактировать: удалено, чтобы сохранить гиперссылки, поиск по тегу декартовы произведения). У этого ответа есть хорошее рекурсивное решение, которое мне было бы трудно улучшить. Вам конкретно нужно итеративное решение вместо рекурсивного?

РЕДАКТИРОВАТЬ:

После просмотра другого итеративного решения по переполнению стека в Perl и ясного объяснения , вот еще одно решение:

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

Вот подход с ленивым итератором, который использует функцию для создания соответствующего типа вывода.

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