查找列表的列表的组合，这些列表加起来等于目标数

本文关键字：列表 于目标 目标 组合 查找 起来 | 更新日期: 2023-09-27 18:13:44

我有一个有趣的问题，我试图解决。老实说，我对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。

我希望这一切都是有意义的，我没有要求太多。我不介意只是朝着一个解决方案的方向，朝着正确的方向推进，而不是整个答案。谢谢!

查找列表的列表的组合，这些列表加起来等于目标数

其他人已经说过，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();
}

听起来像是使用递归而不是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();
            }
        }
    }
}

您可以通过递归实现这一点。这将使用每个列表中的一个值，找到一个总和为目标的组合，如果不存在，则为空。

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

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

相关文章：