Получить все комбинации List (с частичными результатами, тоже) в C #

Обновить

November 2018

Просмотры

1.1k раз

2

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

Пример:

{1, 2, 3}
{4, 5}
{6, 7, 8}

Мне нужно получить:

1
2
3
1/4
1/5
2/4
2/5
3/4
3/5
1/4/6
1/4/7
1/4/8
1/5/6
1/5/7
1/5/8
2/4/6
2/4/7
2/4/8
2/5/6
2/5/7
2/5/8
3/4/6
3/4/7
3/4/8
3/5/6
3/5/7
3/5/8

Мне это нужно в самом быстром способе, если это возможно. У меня уже есть алгоритм, но я хочу, чтобы выяснить, есть ли лучшие альтернативы.

Спасибо.

EDIT: Это мой текущий код. К сожалению для итальянских комментариев.

// Istanzia una lista per contenere le liste di valori
List<List<int>> allLists = new List<List<int>>();

... CODE TO FILL THE LISTS ...

// Esegue un ciclo fino al numero di liste recuperate
for (int listIndex = 0; listIndex < allLists.Count; listIndex++)
{
    // Istanzia una lista per contenere le liste di valori fino allo 
    // step corrente
    List<List<int>> stepLists = new List<List<int>>();

    // Esegue un ciclo sulle liste fino allo step corrente
    for (int stepListIndex = 0; stepListIndex <= listIndex; stepListIndex++)
    {
        // Aggiunge la lista a quelle dello step corrente
        stepLists.Add(allLists[stepListIndex]);
    }

    // Esegue il prodotto vettoriale delle liste specificate
    List<List<int>> crossLists = 
        Mathematics.CrossProduct(stepLists, new List<int>());

    // Carica l'elenco delle combinazioni
    CombinationsCollection allCombinations = 
        new CombinationsCollection(Kernel);
    allCombinations.Load();

    // Esegue un ciclo su ciascuna lista recuperata
    foreach (List<int> crossList in crossLists)
    {
    }
}

... OTHER CODE ...

public static List<List<int>> CrossProduct(
    List<List<int>> lists, 
    List<int> root)
{
    // Istanzia delle liste per contenere le combinazioni
    List<List<int>> results = new List<List<int>>();

    // Se ce n'è almeno una
    if (lists.Count > 0)
    {
        // Recupera la prima lista
        List<int> list = (List<int>)lists[0];

        // Se è rimasta solo una lista
        if (lists.Count == 1)
        {
            // Esegue un ciclo su tutti i valori
            foreach (int value in list)
            {
                // Aggiunge un risultato con radice e valore
                results.Add(new List<int>(root) { value });
            }
        }
        else
        {
            // Esegue un ciclo su ogni valore della lista
            foreach (int value in list)
            {
                // Aggiunge ai risultati la prosecuzione del prodotto 
                // vettoriale dalla lista successiva
                results.AddRange(CrossProduct(
                    lists.GetRange(1, lists.Count - 1), 
                    new List<int>(root) { value })
                );
            }
        }
    }

    return results;
}

3 ответы

5

Вам нужен метод , который возвращает декартово произведение списков плюс частичных результатов (как упомянуто в названии). Вот дисперсия CartesianProductрасширения метода от Eric Липпертого с частичными результатами , как по вашему запросу:

public static IEnumerable<IEnumerable<T>> CrossProduct<T>(
     this IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> accumulator = new[] { Enumerable.Empty<T>() };
    var result = new List<IEnumerable<T>>();
    var firstSequence = true;
    foreach (var sequence in sequences)
    {
        var local = new List<IEnumerable<T>>();
        foreach (var accseq in accumulator)
        {
            if (!firstSequence)
                result.Add(accseq);

            foreach (var item in sequence)
                local.Add(accseq.Concat(new[] { item }));
        }
        firstSequence = false;
        accumulator = local;
    }

    return result.Concat(accumulator);
}

Для ввода данных, при условии:

var items = new[] { 
    new[] { 1, 2, 3 }, 
    new[] { 4, 5 }, 
    new[] { 7, 8, 9 } 
};
var product = items.CrossProduct();

productпеременная будет содержать результат , который вы хотите.

1

Я считаю , что вы ищете является декартово произведение каждого элемента набора мощности «префикс набора» вашего набора последовательностей. Давайте разбить его:

Во-первых, у вас есть набор входных последовательностей:

IEnumerable<IEnumerable<int>> inputSet = new[] {new[] {1,2,3}, new[] {4,5}, new[] {6,7,8}};

«Префикс набор» из inputSet является:

{{}, {1,2,3}, {{1,2,3}, {4,5}}, {{1,2,3}, {4,5}, {6,7,8} }}

Декартово произведение из набора последовательностей дает все комбинации 1 элемент из каждой последовательности.

То, что я верю, что вы ищете: (псевдокод)

foreach (element in the above prefix set)
{
  Print(cartesian product of the sequences in this element);
}

Ниже приведены методы расширения используется для создания декартовых продуктов, наборы питания, и т.д .:

public static class CombinatorialExtensionMethods {
    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
    { 
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
        return sequences.Aggregate( 
            emptyProduct, 
            (accumulator, sequence) =>  
            from accseq in accumulator  
            from item in sequence  
            select accseq.Concat(new[] {item}));                
    }

    public static IEnumerable<IEnumerable<T>> CartesianPower<T>(this IEnumerable<T> sequence, int power) 
    { 
        var sequences = Enumerable.Repeat<IEnumerable<T>>(sequence,power);
        return sequences.CartesianProduct<T>();
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> seq, int k)
    { 
        var sequences = Enumerable.Repeat<IEnumerable<T>>(seq,k);
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
        return sequences.Aggregate( 
            emptyProduct, 
            (accumulator, sequence) =>  
            from accseq in accumulator  
            from item in sequence
            where !accseq.Contains(item)
            select accseq.Concat(new[] {item}));
    }

    public static IEnumerable<IEnumerable<int>> Choose(this IEnumerable<int> seq, int k)
    { 
        var sequences = Enumerable.Repeat<IEnumerable<int>>(seq,k);
        IEnumerable<IEnumerable<int>> emptyProduct = new[] { Enumerable.Empty<int>() }; 
        return sequences.Aggregate( 
            emptyProduct, 
            (accumulator, sequence) =>  
            from accseq in accumulator  
            from item in sequence
            where accseq.All(accitem => accitem.CompareTo(item) < 0)
            select accseq.Concat(new[] {item}));
    }

    public static IEnumerable<IEnumerable<T>> Choose<T>(this IEnumerable<T> seq, int k)
    { 
        IEnumerable<int> idxSequence = Enumerable.Range(0, seq.Count());
        IEnumerable<IEnumerable<int>> idxChoose = idxSequence.Choose(k);
        IEnumerable<IEnumerable<T>> result = Enumerable.Empty<IEnumerable<T>>(); 
        foreach (IEnumerable<int> permutation in idxChoose)
        {
            IEnumerable<T> item = Enumerable.Empty<T>();
            foreach (int index in permutation)
            {
                item = item.Concat(new[] { seq.ElementAt(index) });
            }
            result = result.Concat(new[] { item });
        }
        return result;
    }

    public static IEnumerable<IEnumerable<T>> PowerSet<T>(this IEnumerable<T> seq)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
        for (int i=1; i<=seq.Count(); i++)
        {
            result = result.Concat(seq.Choose<T>(i));
        }

        return result;
    }
}

С их помощью код для примера будет:

IEnumerable<IEnumerable<int>> sequences = new[] {new[] {1,2,3}, new[] {4,5}, new[] {6,7,8}};
IEnumerable<IEnumerable<IEnumerable<int>>> prefixSet = new[] {new[] { Enumerable.Empty<int>() }};

for (int i=0; i<sequences.Count(); i++)
{
    IEnumerable<IEnumerable<int>> prefixSequence = Enumerable.Empty<IEnumerable<int>>();
    for (int j=0; j<=i; j++)
    {
        prefixSequence = prefixSequence.Concat(new[] { sequences.ElementAt(j) });
    }
    prefixSet = prefixSet.Concat(new[] { prefixSequence });
}

foreach (IEnumerable<IEnumerable<int>> item in prefixSet)
{
    Console.WriteLine(item.CartesianProduct<int>());
}
0

Это даст желаемый результат. Не уверен, что производительность по сравнению с исходным кодированием, хотя:

private List<List<int>> test(List<List<int>> lists)
{
    List<List<int>> ret = new List<List<int>>();
    ret.AddRange(from first in lists[0] select new List<int>(new int[] { first }));

    List<List<int>> inner = new List<List<int>>();
    inner.AddRange(from first in lists[0] select new List<int>(new int[] { first }));

    for (int i = 1; i < lists.Count;i++ )
    {
        List<int> l = lists[i];

        var newElements =
          from first in inner
          from second in l
          select new List<int>(first.Concat<int>(new int[] { second }));

        ret.AddRange(newElements);
        inner = newElements.ToList();
    }

    return ret;
}

При вызове с помощью

        List<List<int>> rval = test(
            new List<List<int>>(
                new List<int>[] { 
                    new List<int>(new int[] { 1, 2, 3 }),
                    new List<int>(new int[] { 4, 5 }),
                    new List<int>(new int[] { 6, 7, 8 })
            }));

в результате RVAL содержит элементы в способе требуется.

Возможно, некоторые вещи Linq в там может быть переработано на что-то более легкое или более производительное, я не на твердой почве с этим материалом (поэтому я проверил его, прежде чем я разместил его ;-))