5

Возникли проблемы с понимаем того, как можно реализовать метод для построения декартового произведения, обобщенный на произвольное количество множеств.

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

Для двух множеств понятно, что нужно строить цикл вложенности 2. Для трёх множеств вложенность уже будет 3. Но как это обобщить?

Вообще пишу на Java, но главное алгоритм понять.

3
  • 4
  • 1
    А есть ли какие-нибудь библиотеки, которые сами охотно расправляются с декартовым произведением?
    – Stas0n
    26 окт 2013 в 18:04
  • На плюсах можно было бы просто написать структуру-произведение множеств и итератор для ее элементов, работающий на итераторах от множеств за O(N).
    – user457226
    20 авг 2021 в 1:16

6 ответов 6

2

Для разнообразия подкину ещё одну («ленивую») реализацию на C#, в стиле BCL:

class CompoundEnumerator<T> : IEnumerator<IEnumerable<T>>
{
    IEnumerable<IEnumerator<T>> enumerators;
    bool fresh = true;

    public IEnumerable<T> Current
    {
        get { return enumerators.Select(e => e.Current); }
    }

    object System.Collections.IEnumerator.Current { get { return Current; } }

    public CompoundEnumerator(IEnumerable<IEnumerable<T>> sets)
    {
        enumerators = sets.Select(s => s.GetEnumerator()).ToList();
    }

    public bool MoveNext()
    {
        if (fresh)
        {
            var canMove = enumerators.All(e => e.MoveNext());
            fresh = !canMove;
            return canMove;
        }

        foreach (var e in enumerators)
        {
            if (e.MoveNext())
                return true;
            e.Reset();
            e.MoveNext();
        }
        return false;
    }

    public void Dispose()
    {
        foreach (var e in enumerators)
            e.Dispose();
    }

    public void Reset()
    {
        fresh = true;
        foreach (var e in enumerators)
            e.Reset();
    }
}

static IEnumerable<IEnumerable<T>> CrossProduct<T>(IEnumerable<IEnumerable<T>> sets)
{
    using (var enumerator = new CompoundEnumerator<T>(sets))
    {
        while (enumerator.MoveNext())
            yield return enumerator.Current;
    }
}

Пользоваться так:

static void Main(string[] args)
{
    var list1 = new[] { 'A', 'B', 'C', 'D' };
    var list2 = new[] { '1', '2', '3' };
    var list3 = new[] { '+', '-' };

    foreach (var triple in CrossProduct(new[] { list1, list2, list3 }))
        Console.WriteLine(string.Join(", ", triple));
}
3
  • 1
    @avp: если пожертвовать точностью типов, то можно воспользоваться текущим кодом в виде CrossProduct<object>.
    – VladD
    25 окт 2013 в 14:05
  • @VladD ну во-первых, я вполне неграмотен в C#, поэтому желательно законченный текст (который можно оттранслировать и выполнить), во-вторых: как можно этот вариант распространить на случай четырёх измерений? И причём здесь функциональные языки? Тут или динамическая типизация, или макросы.
    – alexlz
    25 окт 2013 в 16:20
  • @alexlz: вот полный текст: pastebin.com/wcKGwdJG В C# нельзя выразить такую штуку: метод принимает неопределённое количество аргументов; если тип аргументов IEnumerable<T1>, IEnumerable<T2>, ..., IEnumerable<Tn>, то тип возвращаемого значения есть кортеж с типами элементов T1, T2, ..., Tn. Можно лишь для заранее заданного n. (Это сделано в функции CrossProduct2 для n == 3, она легко обобщается на любое n.)
    – VladD
    25 окт 2013 в 16:35
1

Рекурсия подходит. Вот есть пример в С#:

List<Set> CrossProduct(List<Set> sets)
{
    if (sets.Count == 0)
        return sets;
    if (sets.Count == 1)
        return sets[0].Select(x => new Set { x }).ToList();

    Set head = sets.First();
    List<Set> tail = CrossProduct(sets.Skip(1).ToList());
    List<Set> product = new List<Set>();
    for (int i = 0; i < head.Count; i++)
    {
        for (int j = 0; j < tail.Count; j++)
        {
            Set item = new Set();
            item.Add(head[i]);
            item = item.Concat(tail[j]).ToList();
            product.Add(item);
        }
    }
    return product;
}

(Кстате, Set просто List<int>)

0
1

Декартово произведение. Java Stream API + Generics

Различные типы и количества коллекций и их элементов.

Try it online!

public static void main(String[] args) {
    Set<Integer> a = Set.of(1, 2);
    Set<Character> b = Set.of('*', '+');
    List<String> c = List.of("A", "B");

    Set<Set<Object>> cpSet = cartesianProduct(HashSet::new, a, b, c);
    List<List<Object>> cpList = cartesianProduct(ArrayList::new, a, b, c);

    // вывод, порядок может отличаться
    System.out.println(cpSet);
    System.out.println(cpList);
}
/**
 * @param nCol supplier для возвращаемой коллекции
 * @param cols входящий массив коллекций
 * @param <R>  тип возвращаемой коллекции
 * @return декартово произведение множества коллекций
 */
@SuppressWarnings("unchecked")
public static <R extends Collection<?>> R cartesianProduct(
        Supplier nCol, Collection<?>... cols) {
    // проверка supplier не есть null
    if (nCol == null) return null;
    return (R) Arrays.stream(cols)
        // ненулевые и непустые коллекции
        .filter(col -> col != null && col.size() > 0)
        // представить каждый элемент коллекции как одноэлементную коллекцию
        .map(col -> (Collection<Collection<?>>) col.stream()
            .map(e -> Stream.of(e).collect(Collectors.toCollection(nCol)))
            .collect(Collectors.toCollection(nCol)))
        // суммирование пар вложенных коллекций
        .reduce((col1, col2) -> (Collection<Collection<?>>) col1.stream()
            // комбинации вложенных коллекций
            .flatMap(inner1 -> col2.stream()
                // объединить в одну коллекцию
                .map(inner2 -> Stream.of(inner1, inner2)
                    .flatMap(Collection::stream)
                    .collect(Collectors.toCollection(nCol))))
            // коллекция комбинаций
            .collect(Collectors.toCollection(nCol)))
        // иначе пустая коллекция
        .orElse((Collection<Collection<?>>) nCol.get());
}

Вывод, порядок может отличаться:

[[1,A,*],[1,B,*],[1,A,+],[A,2,*],[1,B,+],[2,B,*],[A,2,+],[2,B,+]]
[[2,+,A],[2,+,B],[2,*,A],[2,*,B],[1,+,A],[1,+,B],[1,*,A],[1,*,B]]

См. Implement Cartesian product of several collections by Java StreamMore generic version

0

Декартово произведение, more generic version

Можно использовать более универсальное решение, которое принимает на вход любой тип коллекции Collection и позволяет выбирать типы внутренних и внешних возвращаемых коллекций.

Try it online!

public static void main(String[] args) {
    List<Integer> a = List.of(1, 2);
    List<Long> b = List.of(3L, 4L);
    Set<Float> c = Set.of(5.5F, 6.6F);

    Set<List<Number>> cpListSet = cartesianProduct(
            HashSet::new, ArrayList::new, Set.of(a, b, c));

    List<Set<Number>> cpSetList = cartesianProduct(
            ArrayList::new, HashSet::new, List.of(a, b, c));

    // вывод, порядок может отличаться
    System.out.println(cpListSet);
    System.out.println(cpSetList);
}
/**
 * @param oCol,iCol внеш/внутр supplier для возвращаемой коллекции
 * @param cols      входящяя коллекция коллекций
 * @param <T>       супертип элементов коллекций
 * @param <U>       тип внутр. возвращаемой коллекции
 * @param <R>       тип внеш. возвращаемой коллекции
 * @return декартово произведение множества коллекций
 */
public static <T, U extends Collection<T>, R extends Collection<U>> R
cartesianProduct(Supplier<R> oCol, Supplier<U> iCol,
                 Collection<Collection<? extends T>> cols) {
    // проверка supplier не есть null
    if (oCol == null || iCol == null) return null;
    return cols.stream()
        // ненулевые и непустые коллекции
        .filter(col -> col != null && col.size() > 0)
        // представить каждый элемент коллекции как одноэлементную коллекцию
        .map(col -> col.stream()
            .map(e -> Stream.of(e).collect(Collectors.toCollection(iCol)))
            .collect(Collectors.toCollection(oCol)))
        // суммирование пар вложенных коллекций
        .reduce((col1, col2) -> col1.stream()
            // комбинации вложенных коллекций
            .flatMap(inner1 -> col2.stream()
                // объединить в одну коллекцию
                .map(inner2 -> Stream.of(inner1, inner2)
                    .flatMap(Collection::stream)
                    .collect(Collectors.toCollection(iCol))))
            // коллекция комбинаций
            .collect(Collectors.toCollection(oCol)))
        // иначе пустая коллекция
        .orElse(oCol.get());
}

Вывод, порядок может отличаться:

[[3,2,6.6],[3,2,5.5],[3,1,5.5],[4,2,5.5],[4,1,5.5],[4,1,6.6],[3,1,6.6],[4,2,6.6]]
[[6.6,1,3],[5.5,1,3],[6.6,1,4],[5.5,1,4],[6.6,2,3],[5.5,2,3],[6.6,2,4],[5.5,2,4]]

См. Implement Cartesian product of several collections by Java StreamLess generic version

0

Декартово произведение, три вложенных цикла

  1. Подготавливаем лист листов List<List<T>>, заполненный одним пустым значением. Будем использовать его как промежуточный результат и как финальный результат.

  2. Последовательно перемножаем промежуточный результат с входящими листами попарно. На каждом шаге получаем новый промежуточный результат и двигаемся далее... Получаем финальный результат. Схематически этот итеративный процесс выглядит примерно так:

    res0: [[]]
    col1: [1,2,3]
    ----
    res1: [[1],[2],[3]]
    col2: [4,5,6]
    ----
    res2: [[1,4],[1,5],[1,6],[2,4],[2,5]...,[3,6]]
    col3: [7,8,9]
    ----
    res3: [[1,4,7],[1,4,8],[1,4,9],[1,5,7],[1,5,8]...,[3,6,9]]
    

Try it online!

/**
 * @param cols произвольное количество листов
 * @param <T>  тип элементов листов
 * @return декартово произведение входящих листов
 */
public static <T> List<List<T>> cartesianProduct(List<List<T>> cols) {
    // входящие данные не есть null
    if (cols == null) return Collections.emptyList();
    // промежуточный результат
    List<List<T>> cp = Collections.singletonList(Collections.emptyList());
    // обходим входящие листы
    for (List<T> col : cols) {
        // ненулевые и непустые листы
        if (col == null || col.size() == 0) continue;
        // промежуточный результат для следующей итерации
        List<List<T>> next = new ArrayList<>();
        // строки текущего промежуточного результата
        for (List<T> row : cp) {
            // элементы текущего листа
            for (T el : col) {
                // новая строка для следующего промежуточного результата
                List<T> nRow = new ArrayList<>(row);
                nRow.add(el);
                next.add(nRow);
            }
        }
        // передаём на следующую итерацию
        cp = next;
    }
    // возвращаем итоговый результат
    return cp;
}
public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(1, 2, 3, 4);
    List<Integer> list2 = Arrays.asList(5, 6, 7);
    List<Integer> list3 = Arrays.asList(8, 9);

    // декартово произведение
    List<List<Integer>> cp = cartesianProduct(
            Arrays.asList(list1, list2, list3));

    // вывод по столбцам
    int rows = 6;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cp.size(); j++)
            System.out.print(j % rows == i ? cp.get(j) + " " : "");
        System.out.println();
    }
}

Вывод по столбцам:

[1, 5, 8] [2, 5, 8] [3, 5, 8] [4, 5, 8] 
[1, 5, 9] [2, 5, 9] [3, 5, 9] [4, 5, 9] 
[1, 6, 8] [2, 6, 8] [3, 6, 8] [4, 6, 8] 
[1, 6, 9] [2, 6, 9] [3, 6, 9] [4, 6, 9] 
[1, 7, 8] [2, 7, 8] [3, 7, 8] [4, 7, 8] 
[1, 7, 9] [2, 7, 9] [3, 7, 9] [4, 7, 9] 

См. How to get Cartesian product from multiple lists?Три вложенных цикла JavaScript

0

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

  1. Подготавливаем массив массивов String[][], заполненный одним пустым значением. Будем использовать его как промежуточный результат и как финальный результат.

  2. Последовательно перемножаем промежуточный результат с входящими массивами попарно. На каждом шаге получаем новый промежуточный результат и двигаемся далее... Получаем финальный результат. Схематически этот итеративный процесс выглядит примерно так:

    res0: [[]]
    arr1: [A1,A2,A3]
    ----
    res1: [[A1],[A2],[A3]]
    arr2: [B1,B2,B3]
    ----
    res2: [[A1,B1],[A1,B2],[A1,B3],[A2,B1],[A2,B2]...,[A3,B3]]
    arr3: [C1,C2,C3]
    ----
    res3: [[A1,B1,C1],[A1,B1,C2],[A1,B1,C3],[A1,B2,C1]...,[A3,B3,C3]]
    

Try it online!

public static String[][] cartesianProduct(String[][] arrays) {
    // входящие данные не есть null
    if (arrays == null) return new String[][]{{}};
    // промежуточный результат
    String[][] cp = new String[][]{{}};
    // обходим входящие массивы
    for (int a = 0; a < arrays.length; a++) {
        // текущий массив
        String[] arr = arrays[a];
        // ненулевой и непустой массив
        if (arr == null || arr.length == 0) continue;
        // промежуточный результат для следующей итерации
        String[][] next = new String[cp.length * arr.length][];
        // строки текущего промежуточного результата
        for (int r = 0; r < cp.length; r++) {
            // текущая строка
            String[] row = cp[r];
            // элементы текущего массива
            for (int e = 0; e < arr.length; e++) {
                // текущий элемент
                String el = arr[e];
                // копируем текущую строку в новый массив [длина + 1]
                String[] nRow = Arrays.copyOf(row, row.length + 1);
                nRow[row.length] = el;
                next[r * arr.length + e] = nRow;
            }
        }
        // передаём на следующую итерацию
        cp = next;
    }
    // возвращаем итоговый результат
    return cp;
}
public static void main(String[] args) {
    String[] arr1 = new String[]{"A1", "A2", "A3", "A4"};
    String[] arr2 = new String[]{"B1", "B2", "B3"};
    String[] arr3 = new String[]{"C1", "C2"};

    // декартово произведение
    String[][] cp = cartesianProduct(new String[][]{arr1, arr2, arr3});

    // вывод по столбцам
    int rows = 6;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cp.length; j++)
            System.out.print(j % rows == i ? Arrays.toString(cp[j]) + " " : "");
        System.out.println();
    }
}

Вывод по столбцам:

[A1, B1, C1] [A2, B1, C1] [A3, B1, C1] [A4, B1, C1] 
[A1, B1, C2] [A2, B1, C2] [A3, B1, C2] [A4, B1, C2] 
[A1, B2, C1] [A2, B2, C1] [A3, B2, C1] [A4, B2, C1] 
[A1, B2, C2] [A2, B2, C2] [A3, B2, C2] [A4, B2, C2] 
[A1, B3, C1] [A2, B3, C1] [A3, B3, C1] [A4, B3, C1] 
[A1, B3, C2] [A2, B3, C2] [A3, B3, C2] [A4, B3, C2] 

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.