查找加起来达到目标数字的列表列表的组合

Question

我有一个有趣的问题要解决。老实说，我对 Linq 的了解非常肤浅，我很确定这是一种可以使用基于 Linq 的解决方案最优雅地解决的问题，但到目前为止，我已经尝试了一些事情，但我所掌握的知识很少，但收效甚微.

这很简单：我有一个小数列表列表，我想从列表中找到一个组合，只使用每个列表中的一个元素，加起来达到目标小数。澄清一下：

List<List<decimal>> parentList; // this is the main list I'm drawing from
List<decimal> childList { 1 , 2 , 3 , 4 , 5 }; // each list inside of the main list would look something like this

因此，如果我的 parentList 包含五个 childList，我需要找到一个组合，每个列表只使用一个项目一次。这并不意味着我不能两次使用相同的值，如果 parentList[0] 和 parentList[1] 都包含 3 并且我要添加到 6，{3,3} 将是一个有效的解决方案。但是，如果 parentList[0] 是 { 1 , 2 , 3 } 而 parentList[1] 是 { 4 }，则添加到 6 的唯一有效解决方案是 {2 , 4}，因为第二个列表不包含 3 .

我希望这一切都是有道理的，我没有要求太多。我不介意只是以解决方案的方向为导向，向正确的方向推进而不是整个答案。谢谢！

Answer 1

听起来像是可以使用递归而不是 Linq 来解决的问题。这是一个例子：

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<List<decimal>> listOfLists = new List<List<decimal>>()
            {
                new List<decimal>() { 1, 2, 3 },
                new List<decimal>() { 3, 4, 5 },
                new List<decimal>() { 5, 6, 7 },
            };

            PrintAllCombinationsForTargetValue(listOfLists, 12);
        }

        private static void PrintAllCombinationsForTargetValue(List<List<decimal>> listOfLists, decimal targetValue)
        {
            Stack<decimal> currentCombination = new Stack<decimal>();
            FindNextElement(listOfLists, targetValue, 0, 0, currentCombination);
        }

        private static void FindNextElement(List<List<decimal>> listOfLists, decimal targetValue, int listIndex, decimal trackingValue, Stack<decimal> currentCombination)
        {
            List<decimal> currentList = listOfLists[listIndex];
            foreach (decimal currentValue in currentList)
            {
                decimal currentTrackingValue = trackingValue + currentValue;
                currentCombination.Push(currentValue);

                if (currentTrackingValue < targetValue && listIndex < listOfLists.Count - 1)
                {
                    // There is still la chance that we can get what we want. Let's go to the next list.
                    FindNextElement(listOfLists, targetValue, listIndex + 1, currentTrackingValue, currentCombination);
                }
                else if (currentTrackingValue == targetValue && listIndex == listOfLists.Count - 1)
                {
                    // Found a valid combination!
                    currentCombination.Reverse().ToList().ForEach(element => Console.Write(element + " "));
                    Console.WriteLine();
                }

                currentCombination.Pop();
            }
        }
    }
}

Answer 2

你可以通过递归来实现。这将找到一个总计为目标的组合，使用每个列表中的一个值，或者如果 none 存在则为 null。

public static List<decimal> CombinationSumMatches(
    this IEnumerable<IEnumerable<decimal>> lists, 
    decimal target)
{
    if (lists.Any())
    {
        var firstList = lists.First();
        if (lists.Skip(1).Any())
        {
            foreach (var num in firstList)
            {
                var newTarget = target - num;
                var subCombination = lists.Skip(1).CombinationSumMatches(newTarget);
                if (subCombination != null)
                {
                    subCombination.Insert(0, num);
                    return subCombination;
                }
            }
        }
        else
        {
            if (firstList.Contains(target))
            {
                return new List<decimal> { target };
            }
        }
    }

    return null;
}

这将首先检查是否有任何列表。如果有，那么它会查看第一个，看看是否还有更多。如果有更多，它会遍历第一个列表的每个数字并从目标中减去该值，然后对剩余列表进行递归调用。如果有非空答案，它会插入数字和 returns。现在，如果只有一个列表，那么它只检查列表中的目标，如果找到它，returns 是一个包含该目标值的列表。如果没有列表，或者只有一个没有目标，或者没有匹配子组合的列表，那么它将只是 return null.

Answer 3

正如其他人已经指出的，LINQ 不适合这样的任务。这样的复杂 LINQ 从维护和性能的角度来看都不好。

但直到我内心的极客开心我才停下来！你自找的...

private static IEnumerable<IEnumerable<decimal>> FindCombinations(IEnumerable<IEnumerable<decimal>> listOfLists, decimal target)
{
    return listOfLists.Aggregate(
        Enumerable.Repeat(Enumerable.Empty<decimal>(), 1),
        (acc, seq) =>
            from accseq in acc
            from item in seq
            select accseq.Concat(new[] {item}))
        .Where(x => x.Sum(y => y) == target);
}

这是控制台测试应用程序：

private static void Main(string[] args)
{
    var target = 12;
    var listOfLists = new List<List<decimal>>()
    {
        new List<decimal> { 1, 2, 3 },
        new List<decimal> { 3, 4, 5 },
        new List<decimal> { 5, 6, 7 },
    };

    foreach (var combination in FindCombinations(listOfLists, target))
    {
        Console.WriteLine("{0} = {1}", string.Join(" + ", combination.Select(y => y.ToString(CultureInfo.InvariantCulture))), target);
    }
    Console.ReadKey();
}

查找加起来达到目标数字的列表列表的组合

Finding combinations of list of lists that add up to a target number

c#

linq

combinations

list

查找加起来达到目标​​数字的列表列表的组合

Finding combinations of list of lists that add up to a target number

c#

linq

combinations

list

查找加起来达到目标数字的列表列表的组合