在C#中获取List <List <int >>的所有组合(也包含部分结果)

Question

我需要一个有效的算法来获得整数列表列表的所有可用组合.我也需要部分结果.

一个例子:

{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

如果可能的话,我需要以最快的方式.我已经有了算法,但我想知道是否有更好的选择.

谢谢.

编辑:这是我目前的代码.对不起意大利语的评论.

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

Answer 1

您需要一种方法来返回列表的笛卡尔积和部分结果(如标题中所述).以下是CartesianProductEric Lippert方法扩展的差异,根据您的要求提供部分结果:

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变量将包含你想要的结果.