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

Question

Я хочу вычислить декартово произведение произвольного числа непустых множеств в Java.

Я написал этот итерационный код ...

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

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

Answer 1

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

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

РЕДАКТИРОВАТЬ: код выпущен сейчас.

Sets.cartesianProduct()

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

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

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

Answer 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's 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]
]

Answer 3

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

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

<code>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
 * ...
 * 

* / 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}; для (int [] indexes: new CartesianProduct (length)) { System.out.println (Arrays.toString (indices) // + "" + list1 [indices [0]] // + "," + list2 [indices [1]] // + "," + list3 [indexes [2]]); } }

}

Answer 4

Вот итеративная, ленивая реализация, которую я написал. Интерфейс очень похож на Google Sets.cartesianProduct, но он немного более гибкий: он работает с Iterables вместо Sets. Этот код и его модульные тесты на https://gist.github.com/1911614.

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

* * Каждый результат представляет собой новый массив T, элементы которого относятся к элементам осей. Если * вы предпочитаете список, вы можете вызвать как списки (товар (оси)). *

* Как правило, не меняйте оси во время итерации по своему продукту. Изменения в * Ось может повлиять на продукт или привести к сбою итерации (что обычно плохо). к * Во избежание этого вы можете передавать клоны ваших осей этому методу. *

* Реализация ленива. Этот метод выполняет итерации по осям и возвращает * Итерируемый, который содержит ссылку на каждую ось. Перебирая причины продукта * итерация по каждой оси. Методы каждой оси называются настолько поздними, насколько это практически возможно. * / public static Iterable product (Class resultType, Iterable <? расширяет Iterable <? расширяет T >> осей) { вернуть новый продукт (resultType, newArray (Iterable.class, axes)); } / ** Работает как product (resultType, Arrays.asList (axes)), но немного более эффективно. * / public static Iterable product (Class resultType, Iterable <? extends T> ... axes) { вернуть новый продукт (resultType, axes.clone ()); } / ** * Оберните данные массивы в списки фиксированного размера. Изменения в списках пишут в * массивы. * / public static Iterable > asLists (Iterable <? extends T []> массивы) { return Iterables.transform (массивы, новый AsList ()); } / ** * Arrays.asList, представленный в виде функции (как используется в коллекциях Google). * / открытый статический класс AsList реализует функцию > { @Override public List apply (массив T []) { return Arrays.asList (array); } } / ** Создать общий массив, содержащий ссылки на заданные объекты. * / закрытая статическая T [] newArray (Class <? super T> elementType, Iterable <? extends T> from) { List list = new ArrayList (); для (T f: от) list.add (е); вернуть list.toArray (newArray (elementType, list.size ())); } / ** Создать универсальный массив. * / @SuppressWarnings ( "флажок") private static T [] newArray (Class <? super T> elementType, int length) { return (T []) Array.newInstance (elementType, length); } закрытый статический класс Product реализует Iterable { закрытый финал Class _resultType; закрытый финал Iterable <? расширяет T> [] _axes; / ** Осторожно: данный массив осей содержится в виде ссылки, а не клонируется. * / Product (класс resultType, Iterable <? Extends T> [] оси) { _resultType = resultType; _axes = оси; } @Override public Iterator iterator () { if (_axes.length <= 0) // крайний случай return Collections.singleton (newArray (_resultType, 0)). iterator (); вернуть новый ProductIterator <T>(_ resultType, _axes); } @Override public String toString () { return "Cartesian.product (" + Arrays.toString (_axes) + ")"; } закрытый статический класс ProductIterator реализует Iterator { закрытый финал Iterable <? расширяет T> [] _axes; закрытый финальный итератор <? расширяет T> [] _iterators; // один на ось закрытый финал T [] _result; // копия последнего результата / ** * Минимальный индекс такой, что this.next () вернет массив, содержащий * _iterators [index] .next (). Существуют некоторые специальные значения часовых: NEW означает это * это только что созданный итератор, DONE означает, что все комбинации были * исчерпан (поэтому this.hasNext () == false) и _iterators.length означает, что значение * неизвестно (будет определено this.hasNext). * / private int _nextIndex = NEW; private static final int NEW = -2;приватная статическая final int DONE = -1; / ** Осторожно: данный массив осей содержится в виде ссылки, а не клонируется. * / ProductIterator (класс resultType, Iterable <? Extends T> [] оси) { _axes = оси; _iterators = декартов. > newArray (Iterator.class, _axes.length); for (int a = 0; a <_axes.length; ++ a) { _iterators [a] = axes [a] .iterator (); } _result = newArray (resultType, _iterators.length); } закрытый void close () { _nextIndex = DONE; // Отпустить ссылки, чтобы поощрить сборку мусора: Arrays.fill (_iterators, null); Arrays.fill (_result, null); } @Override public boolean hasNext () { if (_nextIndex == NEW) {// Это первый вызов hasNext (). _nextIndex = 0; // Начни здесь for (Iterator <? extends T> iter: _iterators) { if (! iter.hasNext ()) { близко(); // нет комбинаций перерыв; } } } else if (_nextIndex> = _iterators.length) { // Это первый вызов hasNext () после того, как next () вернул результат. // Определяем _nextIndex, который будет использоваться next (): for (_nextIndex = _iterators.length - 1; _nextIndex> = 0; --_ nextIndex) { Итератор <? extends T> iter = _iterators [_nextIndex]; if (iter.hasNext ()) { перерыв; // Начни здесь } if (_nextIndex == 0) {// Все комбинации созданы. близко(); перерыв; } // Повторить эту ось со следующим значением от предыдущей оси. iter = _axes [_nextIndex] .iterator (); _iterators [_nextIndex] = iter; if (! iter.hasNext ()) {// Упс; эта ось не может быть повторена. близко(); // больше нет комбинаций перерыв; } } } return _nextIndex> = 0; } @Override public T [] next () { if (! hasNext ()) бросить новое 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 5

В следующем ответе используется итерация, а не рекурсия. Он использует тот же класс 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;
    }
}

Answer 6

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

/**
 * cartesian
 *
 * @author ruiqi.zss@alibaba-inc.com
 * @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

Answer 7

Я написал алгоритм рекурсивного декартового произведения для таблицы Strings. Вы можете изменить его, чтобы иметь наборы istead. Ниже приведен алгоритм. Это также объясняется в моей статье

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

Answer 9

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

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

}

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

Answer 10

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

---

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