алгоритм декартова произведения N множеств?

#java #алгоритм

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

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

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

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

Ответы

Ответ 1

Для разнообразия подкину ещё одну («ленивую») реализацию на C#, в стиле BCL:
class CompoundEnumerator : IEnumerator>
{
    IEnumerable> enumerators;
    bool fresh = true;

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

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

    public CompoundEnumerator(IEnumerable> 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> CrossProduct(IEnumerable> sets)
{
    using (var enumerator = new CompoundEnumerator(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));
}


Ответ 2

Рекурсия подходит. Вот есть пример в С#:
List CrossProduct(List 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 tail = CrossProduct(sets.Skip(1).ToList());
    List product = new List();
    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)