Итеративный декартово произведение в Java

Ответ 1

Я написал решение, которое не требует, чтобы вы заполняли большую коллекцию в памяти. К сожалению, требуемый код длиной в сотни строк. Возможно, вам придется подождать, пока он появится в проекте Guava (https://github.com/google/guava), что, я надеюсь, произойдет к концу года. Сожалею. :(

Обратите внимание, что вам может не понадобиться такая утилита, если число наборов, которые вы используете в декартовой системе, является фиксированным числом, известным во время компиляции - вы можете просто использовать это количество вложенных циклов.

ОБНОВЛЕНИЕ: код выпущен сейчас.

Sets.cartesianProduct()

Я думаю, что вы будете очень счастливы с этим. Он только создает отдельные списки, как вы просите их; не заполняет память всеми MxNxPxQ из них.

Если вы хотите проверить источник, он здесь.

Наслаждайтесь!

Ответ 2

Использование Google Guava 19 и Java 8 очень просто:

Скажите, что у вас есть список всех массивов, которые вы хотите связать...

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 Lists.cartesianProduct, since Guava 19
  List<List<String>> cartesianProduct = Lists.cartesianProduct(immutableElements);

  System.out.println(cartesianProduct);
}

Метод создания списка неизменяемых списков выглядит следующим образом:

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

Выход выглядит следующим образом:

[
  [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]
]

Ответ 3

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

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

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

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

Ответ 4

Вот итеративная, ленивая реализация, которую я написал. Интерфейс очень похож на Google Sets.cartesianProduct, но он немного более гибкий: он использует Iterables вместо Sets. Этот код и его модульные тесты находятся на 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:[email protected]">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()";
      }
    }
  }
}

Ответ 5

Индексное решение

Работа с индексами - это простая альтернатива, которая быстрая и эффективная с точки зрения памяти и может обрабатывать любое количество наборов. Реализация Iterable позволяет легко использовать в каждом цикле. См. Метод #main для примера использования.

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

}

Ответ 6

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

EDIT:

После просмотра другого итеративного решения при переполнении стека в 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;
    }

Ответ 7

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

Ключевая абстракция - ввести простой класс 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;
}

}

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

Ответ 8

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

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

Ответ 9

Я написал рекурсивный декартово алгоритм продукта для таблицы строк. Вы можете изменить его, чтобы иметь set istead. Ниже приведен алгоритм. Это также объясняется в моем 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;
}}

Ответ 10

Здесь у меня есть простая реализация только нескольких кодов, и при запуске требуется меньше места https://github.com/treesong/cartesian-set/blob/master/src/main/java/net/ruiqi/collection/CartesianSet.java

/**
 * cartesian
 *
 * @author [email protected]
 * @date 2019/3/28
 */
public class CartesianSet<T> {

    private final T[][] source;

    private final long count;

    public CartesianSet(T[][] source) {
        this.source = source;
        int total = 1;
        for (T[] array : source) {
            total *= array.length;
        }
        this.count = total;
    }

    public long getCount() {
        return count;
    }

    public List<T> get(int index) {
        if (index < 0 || count <= index) { return null; }
        List<T> result = new ArrayList<T>(this.source.length);

        int weight = 1;
        for (T[] row : this.source) {
            int times = index / weight;
            int column = times % row.length;
            result.add(row[column]);
            weight *= row.length;
        }
        return result;
    }
}

и тестовые коды:https://github.com/treesong/cartesian-set/blob/master/src/test/java/net/ruiqi/collection/CartesianSetTest.java