Matching целых чисел в списке

Question

Учитывая У меня есть список целых чисел, как это:

List<int> items = new List<int> {200, 100, 50, 20, 10, 5, 2, 1}; 

и дал мне есть несколько, скажем 13, как я буду найти номера из списка, который добавляет до 13, используя LINQ (или любым другим способом). Список всегда находится в порядке убывания.

Например: 13 = 10 + 2 + 1, поэтому операция даст LINQ меня список целых чисел, содержащих 10,2 и 1.

Если мы не можем найти полный матч, как и в случае 24, это нормально для генерирования исключения.

усилию:

[Test] 
     public void Should_find_subset() 
     { 
      var items = new List<int>() {200, 100, 50, 20, 10, 5, 2, 1}; 

      var find = 13; 
      var result = new List<int>(); 
      var subset = new List<int>(); 
      bool found = false; 

      foreach (var item in items) 
      { 
       if (item == find) 
       { 
        result.Add(item); 
        found = true; 
       } 

       if (item < find) 
       { 
        subset.Add(item); 
        found = subset.Sum() == find; 
       } 

       if (found) 
        break; 
      } 
     } 

Спасибо,

-Mike

Answer 1

в строгом и неэффективный подход с использованием Aggregate:

List<int> items = new List<int> {200, 100, 50, 20, 10, 5, 2, 1}; 
var target = 373; 

var result = items.Aggregate(new List<int>(), (acc, curr) => 
{ 
    if (acc.Sum() + curr <= target) 
     acc.Add(curr); 
    return acc;  
}); 

if(result.Sum() != target) 
    throw new Exception(); // whatever 

результат:

Следует отметить, что такой простой подход не будет работать для всех случаев. Например. Список является 68,50,20, и цель 70. Это приведет к ошибке, а не 50, 20.

Другой неэффективный подход, который обрабатывает такие случаи:

List<int> items = new List<int> {68, 50, 20}; 
var target = 70; 

var result = new List<int>(); 
while(result.Sum() != target && items.Any()) 
{ 
    result = new List<int>(); 
    foreach (var item in items) 
     if (result.Sum() + item <= target) 
      result.Add(item); 
    if(result.Sum() != target) 
     items.Remove(result.Last()); 
} 

if(result.Sum() != target) 
    throw new Exception(); // whatever, no solution found 

результат:

Использование большого списка ввода, вероятно, будет медленным, как черт.

Answer 2

Если я слышу комбинации я предлагаю этот проект: Permutations, Combinations, and Variations

Это рабочий код:

List<int> items = new List<int> { 200, 100, 50, 20, 10, 5, 2, 1 }; 
var allMatchingCombos = new List<IList<int>>(); 
for (int i = 1; i < items.Count; i++) 
{ 
    IEnumerable<IList<int>> matchingCombos = new Combinations<int>(items, i, GenerateOption.WithoutRepetition) 
     .Where(c => c.Sum() == 13); 
    allMatchingCombos.AddRange(matchingCombos); 
} 

foreach(var combo in allMatchingCombos) 
    Console.WriteLine(string.Join(",", combo)); 

Выход: 10,2,1

Edit: Так как вы явно просили LINQ, здесь представляет собой полный LINKified подход:

List<IList<int>> allMatchingCombos = Enumerable.Range(1, items.Count) 
    .SelectMany(i => new Combinations<int>(items, i, GenerateOption.WithoutRepetition) 
        .Where(c => c.Sum() == 13) 
        .ToList()) 
    .ToList();