Декартово произведение произвольных множеств в Java

Ответ 1

Изменить: Предыдущие решения для двух наборов удалены. Подробнее см. В истории изменений.

Вот способ сделать это рекурсивно для произвольного числа множеств:

public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
    if (sets.length < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " +
                sets.length + ")");

    return _cartesianProduct(0, sets);
}

private static Set<Set<Object>> _cartesianProduct(int index, Set<?>... sets) {
    Set<Set<Object>> ret = new HashSet<Set<Object>>();
    if (index == sets.length) {
        ret.add(new HashSet<Object>());
    } else {
        for (Object obj : sets[index]) {
            for (Set<Object> set : _cartesianProduct(index+1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

Обратите внимание, что невозможно сохранить информацию общего типа с возвращаемыми наборами. Если бы вы заранее знали, сколько наборов вы хотели взять на себя, вы могли бы определить общий кортеж, чтобы удержать это много элементов (например, Triple<A, B, C>), но нет способа получить произвольное количество общих параметров в Java.

Ответ 2

Это довольно старый вопрос, но почему бы не использовать Guava cartesianProduct?

Ответ 3

Метод ниже создает декартовое произведение списка списка строк:

protected <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
    List<List<T>> resultLists = new ArrayList<List<T>>();
    if (lists.size() == 0) {
        resultLists.add(new ArrayList<T>());
        return resultLists;
    } else {
        List<T> firstList = lists.get(0);
        List<List<T>> remainingLists = cartesianProduct(lists.subList(1, lists.size()));
        for (T condition : firstList) {
            for (List<T> remainingList : remainingLists) {
                ArrayList<T> resultList = new ArrayList<T>();
                resultList.add(condition);
                resultList.addAll(remainingList);
                resultLists.add(resultList);
            }
        }
    }
    return resultLists;
}

Пример:

System.out.println(cartesianProduct(Arrays.asList(Arrays.asList("Apple", "Banana"), Arrays.asList("Red", "Green", "Blue"))));

даст следующее:

[[Apple, Red], [Apple, Green], [Apple, Blue], [Banana, Red], [Banana, Green], [Banana, Blue]]

Ответ 4

Количество наборов может меняться, поэтому я не может сделать это во вложенном цикле foreach.

Два подсказки:

• A x B x C = A x (B x C)
• Рекурсия

Ответ 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

Вот Iterable, который позволяет использовать упрощенный цикл for:

import java.util.*;

// let begin with the demo. Instead of Person and Gift, 
// I use the well known char and int. 
class CartesianIteratorTest {

    public static void main (String[] args) {
        List <Object> lc = Arrays.asList (new Object [] {'A', 'B', 'C', 'D'});
        List <Object> lC = Arrays.asList (new Object [] {'a', 'b', 'c'});   
        List <Object> li = Arrays.asList (new Object [] {1, 2, 3, 4});
            // sometimes, a generic solution like List <List <String>>
            // might be possible to use - typically, a mixture of types is 
            // the common nominator 
        List <List <Object>> llo = new ArrayList <List <Object>> ();
        llo.add (lc);
        llo.add (lC);
        llo.add (li);

        // Preparing the List of Lists is some work, but then ...    
        CartesianIterable <Object> ci = new CartesianIterable <Object> (llo);

        for (List <Object> lo: ci)
            show (lo);
    }

    public static void show (List <Object> lo) {
        System.out.print ("(");
        for (Object o: lo)
            System.out.print (o + ", ");
        System.out.println (")");
    }
}

Как это делается? Нам нужен Iterable, чтобы использовать упрощенную for-loop, и Iterator должен быть возвращен из Iterable. Мы возвращаем список объектов - это может быть набор вместо списка, но Set не имеет индексированного доступа, поэтому было бы немного сложнее реализовать его с помощью Set вместо List. Вместо общего решения объект был бы прекрасен для многих целей, но дженерики допускают больше ограничений.

class CartesianIterator <T> implements Iterator <List <T>> {

    private final List <List <T>> lilio;    
    private int current = 0;
    private final long last;

    public CartesianIterator (final List <List <T>> llo) {
        lilio = llo;
        long product = 1L;
        for (List <T> lio: lilio)
            product *= lio.size ();
        last = product;
    } 

    public boolean hasNext () {
        return current != last;
    }

    public List <T> next () {
        ++current;
        return get (current - 1, lilio);
    }

    public void remove () {
        ++current;
    }

    private List<T> get (final int n, final List <List <T>> lili) {
        switch (lili.size ())
        {
            case 0: return new ArrayList <T> (); // no break past return;
            default: {
                List <T> inner = lili.get (0);
                List <T> lo = new ArrayList <T> ();
                lo.add (inner.get (n % inner.size ()));
                lo.addAll (get (n / inner.size (), lili.subList (1, lili.size ())));
                return lo;
            }
        }
    }
}

Математическая работа выполняется в методе get. Подумайте о двух наборах из 10 элементов. У вас есть в общей сложности 100 комбинаций, перечисляемых с 00, 01, 02,... 10,... до 99. Для 5 X 10 элементов 50 для 2 X 3 элементов 6 комбинаций. По модулю размера подсписок помогает выбрать один элемент для каждой итерации.

Итерируемое, самое интересное здесь:

class CartesianIterable <T> implements Iterable <List <T>> {

    private List <List <T>> lilio;  

    public CartesianIterable (List <List <T>> llo) {
        lilio = llo;
    }

    public Iterator <List <T>> iterator () {
        return new CartesianIterator <T> (lilio);
    }
}

Чтобы реализовать Iterable, который позволяет для каждого типа цикла, мы должны реализовать iterator(), а для Iterator мы должны реализовать hasNext(), next() и remove().

Результат:

(A, a, 1, )
(B, a, 1, )
(C, a, 1, )
(D, a, 1, )
(A, b, 1, )
(B, b, 1, )
(C, b, 1, )
(D, b, 1, )
...
(A, a, 2, )
...
(C, c, 4, )
(D, c, 4, )

Ответ 7

Вот Iterator, который дает декартово произведение двумерного массива, где компоненты массивов представляют собой множества из вопроса (всегда можно преобразовать фактические Set в массивы):

public class CartesianIterator<T> implements Iterator<T[]> {
    private final T[][] sets;
    private final IntFunction<T[]> arrayConstructor;

    private int count = 0;
    private T[] next = null;

    public CartesianIterator(T[][] sets, IntFunction<T[]> arrayConstructor) {
        Objects.requireNonNull(sets);
        Objects.requireNonNull(arrayConstructor);

        this.sets = copySets(sets);
        this.arrayConstructor = arrayConstructor;
    }

    private static <T> T[][] copySets(T[][] sets) {
        // If any of the arrays are empty, then the entire iterator is empty.
        // This prevents division by zero in `hasNext`.
        for (T[] set : sets) {
            if (set.length == 0) {
                return Arrays.copyOf(sets, 0);
            }
        }
        return sets.clone();
    }

    @Override
    public boolean hasNext() {
        if (next != null) {
            return true;
        }

        int tmp = count;
        T[] value = arrayConstructor.apply(sets.length);
        for (int i = 0; i < value.length; i++) {
            T[] set = sets[i];

            int radix = set.length;
            int index = tmp % radix;

            value[i] = set[index];

            tmp /= radix;
        }

        if (tmp != 0) {
            // Overflow.
            return false;
        }

        next = value;
        count++;

        return true;
    }

    @Override
    public T[] next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }

        T[] tmp = next;
        next = null;
        return tmp;
    }
}

Основная идея состоит в том, чтобы рассматривать count как число с несколькими радиусами (цифра i имеет свой собственный радиус, который равен длине i 'th "set" ). Всякий раз, когда мы должны разрешать next (то есть, когда hasNext() вызывается, а next - null), мы разлагаем число на его цифры в этом мультирадикале. Эти цифры теперь используются как индексы, из которых мы рисуем элементы из разных множеств.

Пример использования:

String[] a = { "a", "b", "c"};
String[] b = { "X" };
String[] c = { "r", "s" };

String[][] abc = { a, b, c };

Iterable<String[]> it = () -> new CartesianIterator<>(abc, String[]::new);
for (String[] s : it) {
    System.out.println(Arrays.toString(s));
}

Вывод:

[a, X, r]
[b, X, r]
[c, X, r]
[a, X, s]
[b, X, s]
[c, X, s]

Если вам не нравятся массивы, код тривиально конвертируется в использование коллекций.

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

Ответ 8

Да, есть Функциональная Java.

Для набора (ов):

s.bind(P.p2(), s);

Ответ 9

Объем памяти (и обработки), необходимый для декартова продукта, может быстро выйти из-под контроля. Наивная реализация может исчерпать память и занять много времени. Было бы неплохо узнать, какие операции вы планируете выполнять в таком наборе, чтобы предложить стратегию реализации.

В любом случае сделайте что-то вроде Sets.SetView в коллекциях google. Это набор, который подкрепляется другими наборами по мере их добавления. Идея их проблемы заключается в том, чтобы избежать вызова addAll. Идея вашей проблемы состоит в том, чтобы избежать добавления NxMxK ​​в набор.

Коллекции Google можно найти здесь, и упомянутый класс здесь

Ответ 10

как насчет использования odl.com.google.common18.collect.Sets и вызова метода Sets.cartesianProduct()