Найти все подмножества K-размер с суммой s из мешка п размера дублирующих несортированных положительных целых чисел

Question

Пожалуйста, обратите внимание, что это необходимо для проекта C# .NET 2.0 (Linq не допускается).

Я знаю, что очень похожие вопросы были заданы здесь, и я уже создал какой-то рабочий код (см. Ниже), но по-прежнему хотел бы дать совет относительно того, как сделать алгоритм быстрее заданными условиями k и s.

Это то, что я узнал до сих пор: Динамическое программирование - это наиболее эффективный способ поиска ONE (не всех) подмножеств. Пожалуйста, поправьте меня, если я ошибаюсь. И есть ли способ повторного вызова кода DP для создания более новых подмножеств до тех пор, пока сумка (установленная с дубликатами) не будет исчерпана?

Если нет, то есть ли способ ускорить рекурсивный алгоритм возврата назад, который ниже, чем он создает то, что мне нужно, но работает в O (2^n), я думаю, принимая во внимание s и k?

Вот мой фиксированный мешок чисел, которые никогда не изменятся с п = 114 и диапазон номеров от 3 до 286:

int[] numbers = new int[] 
    { 
     7, 286, 200, 176, 120, 165, 206, 75, 129, 109, 
     123, 111, 43, 52, 99, 128, 111, 110, 98, 135, 
     112, 78, 118, 64, 77, 227, 93, 88, 69, 60, 
     34, 30, 73, 54, 45, 83, 182, 88, 75, 85, 
     54, 53, 89, 59, 37, 35, 38, 29, 18, 45, 
     60, 49, 62, 55, 78, 96, 29, 22, 24, 13, 
     14, 11, 11, 18, 12, 12, 30, 52, 52, 44, 
     28, 28, 20, 56, 40, 31, 50, 40, 46, 42, 
     29, 19, 36, 25, 22, 17, 19, 26, 30, 20, 
     15, 21, 11, 8, 8, 19, 5, 8, 8, 11, 
     11, 8, 3, 9, 5, 4, 7, 3, 6, 3, 
     5, 4, 5, 6 
    }; 

Требования

• предельное пространство в 2-3 Гбайт max, но время должно быть O (n^something) не (что-то^n).

• Сумка не должна сортироваться, а дублировать нельзя удалять.

• Результат должен быть индексом числа в соответствующем подмножестве , а не сами числа (так как у нас есть дубликаты).

Динамическое программирование Покушение

Вот C# динамического программирования версия адаптировано из ответа на подобный вопрос здесь: stackoverflow.com

using System; 
using System.Collections.Generic; 

namespace Utilities 
{ 
    public static class Combinations 
    { 
     private static Dictionary<int, bool> m_memo = new Dictionary<int, bool>(); 
     private static Dictionary<int, KeyValuePair<int, int>> m_previous = new Dictionary<int, KeyValuePair<int, int>>(); 
     static Combinations() 
     { 
      m_memo.Clear(); 
      m_previous.Clear(); 
      m_memo[0] = true; 
      m_previous[0] = new KeyValuePair<int, int>(-1, 0); 

     } 

     public static bool FindSubset(IList<int> set, int sum) 
     { 
      //m_memo.Clear(); 
      //m_previous.Clear(); 
      //m_memo[0] = true; 
      //m_previous[0] = new KeyValuePair<int, int>(-1, 0); 

      for (int i = 0; i < set.Count; ++i) 
      { 
       int num = set[i]; 
       for (int s = sum; s >= num; --s) 
       { 
        if (m_memo.ContainsKey(s - num) && m_memo[s - num] == true) 
        { 
         m_memo[s] = true; 

         if (!m_previous.ContainsKey(s)) 
         { 
          m_previous[s] = new KeyValuePair<int, int>(i, num); 
         } 
        } 
       } 
      } 

      return m_memo.ContainsKey(sum) && m_memo[sum]; 
     } 
     public static IEnumerable<int> GetLastIndex(int sum) 
     { 
      while (m_previous[sum].Key != -1) 
      { 
       yield return m_previous[sum].Key; 
       sum -= m_previous[sum].Value; 
      } 
     } 

     public static void SubsetSumMain(string[] args) 
     { 
      int[] numbers = new int[] 
     { 
      7, 286, 200, 176, 120, 165, 206, 75, 129, 109, 
      123, 111, 43, 52, 99, 128, 111, 110, 98, 135, 
      112, 78, 118, 64, 77, 227, 93, 88, 69, 60, 
      34, 30, 73, 54, 45, 83, 182, 88, 75, 85, 
      54, 53, 89, 59, 37, 35, 38, 29, 18, 45, 
      60, 49, 62, 55, 78, 96, 29, 22, 24, 13, 
      14, 11, 11, 18, 12, 12, 30, 52, 52, 44, 
      28, 28, 20, 56, 40, 31, 50, 40, 46, 42, 
      29, 19, 36, 25, 22, 17, 19, 26, 30, 20, 
      15, 21, 11, 8, 8, 19, 5, 8, 8, 11, 
      11, 8, 3, 9, 5, 4, 7, 3, 6, 3, 
      5, 4, 5, 6 
     }; 

      int sum = 400; 
      //int size = 4; // don't know to use in dynamic programming 

      // call dynamic programming 
      if (Numbers.FindSubset(numbers, sum)) 
      { 
       foreach (int index in Numbers.GetLastIndex(sum)) 
       { 
        Console.Write((index + 1) + "." + numbers[index] + "\t"); 
       } 
       Console.WriteLine(); 
      } 
      Console.WriteLine(); 

      Console.ReadKey(); 
     } 
    } 
} 

Рекурсивный Программирование Покушение

и здесь рекурсивное программирование C# ve rsion адаптирован из ответа на подобный вопрос здесь: stackoverflow.com

using System; 
using System.Collections.Generic; 

namespace Utilities 
{ 
    public static class Combinations 
    { 
     private static int s_count = 0; 
     public static int CountSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result) 
     { 
      if ((numbers.Length <= index) || (current > sum)) return 0; 
      if (result == null) result = new List<int>(); 

      List<int> temp = new List<int>(result); 
      if (current + numbers[index] == sum) 
      { 
       temp.Add(index); 
       if ((size == 0) || (temp.Count == size)) 
       { 
        s_count++; 
       } 
      } 
      else if (current + numbers[index] < sum) 
      { 
       temp.Add(index); 
       CountSubsets(numbers, index + 1, current + numbers[index], sum, size, temp); 
      } 

      CountSubsets(numbers, index + 1, current, sum, size, result); 
      return s_count; 
     } 

     private static List<List<int>> m_subsets = new List<List<int>>(); 
     public static List<List<int>> FindSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result) 
     { 
      if ((numbers.Length <= index) || (current > sum)) return m_subsets; 
      if (result == null) result = new List<int>(); 

      List<int> temp = new List<int>(result); 
      if (current + numbers[index] == sum) 
      { 
       temp.Add(index); 
       if ((size == 0) || (temp.Count == size)) 
       { 
        m_subsets.Add(temp); 
       } 
      } 
      else if (current + numbers[index] < sum) 
      { 
       temp.Add(index); 
       FindSubsets(numbers, index + 1, current + numbers[index], sum, size, temp); 
      } 

      FindSubsets(numbers, index + 1, current, sum, size, result); 

      return m_subsets; 
     } 

     public static void SubsetSumMain(string[] args) 
     { 
      int[] numbers = new int[] 
     { 
      7, 286, 200, 176, 120, 165, 206, 75, 129, 109, 
      123, 111, 43, 52, 99, 128, 111, 110, 98, 135, 
      112, 78, 118, 64, 77, 227, 93, 88, 69, 60, 
      34, 30, 73, 54, 45, 83, 182, 88, 75, 85, 
      54, 53, 89, 59, 37, 35, 38, 29, 18, 45, 
      60, 49, 62, 55, 78, 96, 29, 22, 24, 13, 
      14, 11, 11, 18, 12, 12, 30, 52, 52, 44, 
      28, 28, 20, 56, 40, 31, 50, 40, 46, 42, 
      29, 19, 36, 25, 22, 17, 19, 26, 30, 20, 
      15, 21, 11, 8, 8, 19, 5, 8, 8, 11, 
      11, 8, 3, 9, 5, 4, 7, 3, 6, 3, 
      5, 4, 5, 6 
     }; 

      int sum = 17; 
      int size = 2; 

      // call backtracking recursive programming 
      Console.WriteLine("CountSubsets"); 
      int count = Numbers.CountSubsets(numbers, 0, 0, sum, size, null); 
      Console.WriteLine("Count = " + count); 
      Console.WriteLine(); 

      // call backtracking recursive programming 
      Console.WriteLine("FindSubsets"); 
      List<List<int>> subsets = Numbers.FindSubsets(numbers, 0, 0, sum, size, null); 
      for (int i = 0; i < subsets.Count; i++) 
      { 
       if (subsets[i] != null) 
       { 
        Console.Write((i + 1).ToString() + ":\t"); 
        for (int j = 0; j < subsets[i].Count; j++) 
        { 
         int index = subsets[i][j]; 
         Console.Write((index + 1) + "." + numbers[index] + " "); 
        } 
        Console.WriteLine(); 
       } 
      } 
      Console.WriteLine("Count = " + subsets.Count); 

      Console.ReadKey(); 
     } 
    } 
} 

Пожалуйста, дайте мне знать, как ограничить динамическую версию программирования для подмножеств размера к и если я могу назвать это несколько раз, так что возвращает различные подмножества на каждый вызов до тех пор, пока не будет больше совпадающих подмножеств.

Также я не уверен, где инициализировать памятку DP-алгоритма. Я сделал это в статическом конструкторе, который автоматически запускается при доступе к любому методу. Является ли это правильным местом инициализации или нужно ли его перемещать внутри метода FindSunset() [закомментировано]?

Что касается рекурсивной версии, то это откат? и как мы можем ускорить его. Он работает правильно и учитывает k и s, но полностью неэффективен.

Давайте сделаем эту тему матерью всех вопросов, связанных с C# SubsetSum!

Answer 1

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

Я старался использовать только функции .Net Framework 2.0. Могу добавить визуальное объяснение позже, но комментариев должно быть достаточно.

class Puzzle 
{ 
    private readonly int[] _tailSums; 
    public readonly SubsetElement[] Elements; 
    public readonly int N; 

    public Puzzle(int[] numbers) 
    { 
     // Set N and make Elements array 
     // (to remember the original index of each element) 
     this.N = numbers.Length; 
     this.Elements = new SubsetElement[this.N]; 

     for (var i = 0; i < this.N; i++) 
     { 
      this.Elements[i] = new SubsetElement(numbers[i], i); 
     } 

     // Sort Elements descendingly by their Number value 
     Array.Sort(this.Elements, (a, b) => b.Number.CompareTo(a.Number)); 

     // Save tail-sums to allow immediate access by index 
     // Allow immedate calculation by index = N, to sum 0 
     this._tailSums = new int[this.N + 1]; 
     var sum = 0; 

     for (var i = this.N - 1; i >= 0; i--) 
     { 
      this._tailSums[i] = sum += this.Elements[i].Number; 
     } 
    } 

    public void Solve(int s, Action<SubsetElement[]> callback) 
    { 
     for (var k = 1; k <= this.N; k++) 
      this.Solve(k, s, callback); 
    } 

    public void Solve(int k, int s, Action<SubsetElement[]> callback) 
    { 
     this.ScanSubsets(0, k, s, new List<SubsetElement>(), callback); 
    } 

    private void ScanSubsets(int startIndex, int k, int s, 
          List<SubsetElement> subset, Action<SubsetElement[]> cb) 
    { 
     // No more numbers to add, and current subset is guranteed to be valid 
     if (k == 0) 
     { 
      // Callback with current subset 
      cb(subset.ToArray()); 
      return; 
     } 

     // Sum the smallest k elements 
     var minSubsetStartIndex = this.N - k; 
     var minSum = this._tailSums[minSubssetStartIndex]; 

     // Smallest possible sum is greater than wanted sum, 
     // so a valid subset cannot be found 
     if (minSum > s) 
     { 
      return; 
     } 

     // Find largest number that satisfies the condition 
     // that a valid subset can be found 
     minSum -= this.Elements[minSubsetStartIndex].Number; 

     // But remember the last index that satisfies the condition 
     var minSubsetEndIndex = minSubsetStartIndex; 

     while (minSubsetStartIndex > startIndex && 
       minSum + this.Elements[minSubsetStartIndex - 1].Number <= s) 
     { 
      minSubsetStartIndex--; 
     } 

     // Find the first number in the sorted sequence that is 
     // the largest number we just found (in case of duplicates) 
     while (minSubsetStartIndex > startIndex && 
       Elements[minSubsetStartIndex] == Elements[minSubsetStartIndex - 1]) 
     { 
      minSubsetStartIndex--; 
     } 

     // [minSubsetStartIndex .. maxSubsetEndIndex] is the 
     // full range we must check in recursion 

     for (var subsetStartIndex = minSubsetStartIndex; 
      subsetStartIndex <= minSubsetEndIndex; 
      subsetStartIndex++) 
     { 
      // Find the largest possible sum, which is the sum of the 
      // k first elements, starting at current subsetStartIndex 
      var maxSum = this._tailSums[subsetStartIndex] - 
         this._tailSums[subsetStartIndex + k]; 

      // The largest possible sum is less than the wanted sum, 
      // so a valid subset cannot be found 
      if (maxSum < s) 
      { 
       return; 
      } 

      // Add current number to the subset 
      var x = this.Elements[subsetStartIndex]; 
      subset.Add(x); 

      // Recurse through the sub-problem to the right 
      this.ScanSubsets(subsetStartIndex + 1, k - 1, s - x.Number, subset, cb); 

      // Remove current number and continue loop 
      subset.RemoveAt(subset.Count - 1); 
     } 
    } 

    public sealed class SubsetElement 
    { 
     public readonly int Number; 
     public readonly int Index; 

     public SubsetElement(int number, int index) 
     { 
      this.Number = number; 
      this.Index = index; 
     } 

     public override string ToString() 
     { 
      return string.Format("{0}({1})", this.Number, this.Index); 
     } 
    } 
} 

Использование и тестирование производительности:

private static void Main() 
{ 
    var sw = Stopwatch.StartNew(); 
    var puzzle = new Puzzle(new[] 
     { 
      7, 286, 200, 176, 120, 165, 206, 75, 129, 109, 
      123, 111, 43, 52, 99, 128, 111, 110, 98, 135, 
      112, 78, 118, 64, 77, 227, 93, 88, 69, 60, 
      34, 30, 73, 54, 45, 83, 182, 88, 75, 85, 
      54, 53, 89, 59, 37, 35, 38, 29, 18, 45, 
      60, 49, 62, 55, 78, 96, 29, 22, 24, 13, 
      14, 11, 11, 18, 12, 12, 30, 52, 52, 44, 
      28, 28, 20, 56, 40, 31, 50, 40, 46, 42, 
      29, 19, 36, 25, 22, 17, 19, 26, 30, 20, 
      15, 21, 11, 8, 8, 19, 5, 8, 8, 11, 
      11, 8, 3, 9, 5, 4, 7, 3, 6, 3, 
      5, 4, 5, 6 
     }); 

    puzzle.Solve(2, 17, PuzzleOnSubsetFound); 

    sw.Stop(); 
    Console.WriteLine("Subsets found: " + _subsetsCount); 
    Console.WriteLine(sw.Elapsed); 
} 

private static int _subsetsCount; 

private static void PuzzleOnSubsetFound(Puzzle.SubsetElement[] subset) 
{ 
    _subsetsCount++; 
    return; // Skip prints when speed-testing 

    foreach (var el in subset) 
    { 
     Console.Write(el.ToString()); 
     Console.Write(" "); 
    } 

    Console.WriteLine(); 
} 

Выход:

Каждая строка является найдено подмножество, числа в() являются оригинальный индекс числа, используемый в подмножество

14 (60) 3 (107)
14 (60) 3 (109)
14 (60) 3 (102)
13 (59) 4 (105)
13 (59) 4 (111)
12 (64) 5 (96)
12 (64) 5 (104)
12 (64) 5 (112)
12 (64) 5 (110)
12 (65) 5 (96)
12 (65) 5 (104)
12 (65) 5 (112)
12 (65) 5 (110)
11 (100) 6 (108)
11 (100) 6 (113)
11 (61) 6 (108)
11 (61) 6 (113)
11 (92) 6 (108)
11 (92) 6 (113)
11 (62) 6 (108)
11 (62) 6 (113)
11 (99) 6 (108)
11 (99) 6 (113)
9 (103) 8 (93)
9 (103) 8 (94)
9 (103) 8 (97)
9 (103) 8 (98)
9 (103) 8 (101)
Подмножества найдено: 28
00: 00: 00,0017020 (измеряется, когда не выполняется печать)

---

Чем выше k, тем больше отключений могут быть сделаны , Это когда вы увидите существенную разницу в производительности. Ваш текущий код (рекурсивная версия) также выполняет значительно медленнее, когда s идет выше.

С k=5, s=60
Ваш текущий код: найдено 45070 подмножества в 2,8602923 секунды
Мой код: найдено 45070 подмножества в 0,0116727 секунды
Это 99,6% улучшения Быстродействие

Answer 2

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

Самый быстрый алгоритм для k комбинаций, удовлетворяя ваше дело, будет:

for (var i1 = 0; i1 <= n; i1++) 
{ 
    for (var i2 = i1 + 1; i2 <= n; i2++) 
    { 
     for (var i3 = i2 + 1; i3 <= n; i3++) 
     { 
      ... 

      for (var ik = iOneBeforeK + 1; ik <= n; ik++) 
      { 
       if (arr[i1] + arr[i2] + ... + arr[ik] == sum) 
       { 
        // this is a valid subset 
       } 
      } 
     } 
    } 
} 

Но вы говорите о числах и суммируя их, означает, что вы могли бы сделать обрезаний с более умным алгоритмом.

Поскольку все числа положительны, вы знаете, что если одно число достаточно велико, вы не можете добавить к нему никаких положительных чисел и суммировать его до s. Учитывая s=6 и k=4, наибольшее число, которое необходимо включить в поиск, - s-k+1=3. 3+1+1+1 - k номера, 1 - ваше минимальное возможное количество, сумма до 6. Любое число выше 3 не может иметь 3 других позитивов добавил к нему, и есть на сумму < = 6.

Но ждать, минимальная возможная величина не 1, это 3. Это даже лучше. Предположим, что k=10, n=60, min=3. «Сценарий с наивысшим числом» - x+min(k-1)=n ->x=60-3*9=33. Таким образом, наибольшее число, чтобы даже рассмотреть, было бы 33.

Это сокращает количество соответствующих чисел в массиве, чтобы рассмотреть, следовательно, он сокращает количество комбинаций, которые нужно искать.

Но это становится еще лучше. Предположите k=10, n=60, min=3. Первое число в массиве - 20, поэтому оно релевантно и должно быть проверено. Давайте найдем соответствующие подмножества, которые включают в себя: 20:
Появляется новая «головоломка»! k=10-1, n=60-20, min=3. Теперь вы можете CutOff много чисел от subpuzzle, и снова и снова, которые каждый шаг в.

Это может быть еще более улучшены путем вычисления среднего значения k-1 низких чисел в subpuzzle и использовать его в качестве min.

можно улучшить еще дальше от предварительного вычисления среднего k низкие цифры в subpuzzle [0..n] и k-1 низкое число в среднем subpuzzle [1..n] и k-2 самые низкие цифры в среднем subpuzzle [2..n] и так далее, и использовать их вместо перерасчета то же самое вещество снова и снова в каждой оценке подложек.

Answer 3

Попробуйте использовать приведенный ниже код. Извините, у меня не было времени на оптимизацию кода. Вы можете сравнить все методы, которые у вас есть, и сделать вывод, который быстрее, не забывайте делиться результатами.

C# (вы можете попытаться избавиться от списка может быть, это даст вам повышение производительности:

public static IEnumerable<List<int>> findSubsetsWithLengthKAndSumS2(Tuple<int, int> ks, List<int> set, List<int> subSet, List<int> subSetIndex) 
    { 
     if (ks.Item1 == 0 && ks.Item2 == 0) 
     { 
      var res = new List<List<int>>(); 
      res.Add(subSetIndex); 
      return res; 
     } 
     else if (ks.Item1 > 0 && ks.Item2 > 0) 
     { 
      var res = set.Select((x, i) => 
      { 
       var newSubset = subSet.Select(y => y).ToList(); 
       newSubset.Add(x); 

       var newSubsetIndex = subSetIndex.Select(y => y).ToList(); 
       newSubsetIndex.Add(i); 

       var newSet = set.Skip(i).ToList(); 
       return findSubsetsWithLengthKAndSumS2(Tuple.Create(ks.Item1 - 1, ks.Item2 - x), newSet, newSubset, newSubsetIndex).ToList(); 
      } 
      ).SelectMany(x => x).ToList(); 
      return res; 
     } 
     else 
      return new List<List<int>>(); 
    } 
... 
      var res = findSubsetsWithLengthKAndSumS2(Tuple.Create(2, 293), numbers.ToList(), new List<int>(), new List<int>()); 

F # (я добавил его Просто для удовольствия =), он не оптимизирован слишком, я считаю, самый медленный место в коде «пропустить»):

let skip (list:List<int>) index = 
    list |> List.mapi (fun i x -> if i > index then Some(x) else None) |> List.filter (fun x -> x.IsSome) |> List.map (fun x -> x.Value) 

let rec findSubsetsWithLengthKAndSumS (ks:int*int) (set:list<int>) (subSet:list<int>) = 
    [ 
     match ks with 
     |0,0 -> yield subSet 
     | x,y when x > 0 && y > 0 -> yield! set |> List.mapi (fun i x-> findSubsetsWithLengthKAndSumS ((fst ks)-1,(snd ks)-x) (skip set i) (x::subSet)) |> Seq.concat 
     | _,_-> yield [] 
    ] 
... 
    let res = Subsets.findSubsetsWithLengthKAndSumS (2,293) numbers [] |> List.filter (fun x-> x.Length >0) 

Я считаю, что это итерационный вариант будет быстрее, чем другие во много раз. Он использует .net 2.0:

public delegate IEnumerable< IEnumerable<int> > findSubset(); 

    public delegate bool findSubsetsIterativeFilter(int[] sourceSet, int[] indiciesToSum, int expected); 

    public static bool Summ(int[] sourceSet, int[] indicies, int expected) 
    { 
     var sum = 0; 
     for(int i = 0; i < indicies.Length; i++) 
      sum += sourceSet[ indicies[ i ] ]; 
     return sum == expected; 
    } 

    public static IEnumerable< IEnumerable<int> > findSubsetsIterative(int k, int[] sourceSet, findSubsetsIterativeFilter specialCondition, int expected) 
    { 
     var a = new int[ k ]; 
     for(int i = 0; i < k; i++) 
      a[ i ] = i; 

     var p = k - 1; 
     while(p >= 0) 
     { 
      if(specialCondition(sourceSet, a, expected)) 
       yield return (int[])a.Clone(); 
      p = (a[ k - 1 ] == sourceSet.Length - 1) ? p - 1 : k - 1; 
      if(p >= 0) 
       for(int i = k - 1; i >= p; i--) 
        a[ i ] = a[ p ] + i - p + 1; 
     } 
    } 
    ... 
     findSubsetsIterative(2, a, Summ, 293); 

я измерил мой код и Yorye-х, и вот что я получаю. Мой код быстрее в 4-10x. Вы использовали «findSubsetsIterative» из моего ответа в своих экспериментах?

findSubsetsIterative (4, GenerateSOurceData (1), Сумм, 400) Истекшее: 00: 00: 00,0012113 puzzle.Solve (4, 400, PuzzleOnSubsetFound) Прошедшее: 00: 00: 00,0046170

findSubsetsIterative (5, GenerateSOurceData (1), Сумм, 60) Прошедшее: 00: 00: 00,0012960 puzzle.Solve (5, 60, PuzzleOnSubsetFound) Прошедшее: 00: 00: 00,0108568

Здесь я увеличил входящий массив в 5х (просто скопировал массив 5 раз в новый большой массив): findSubsetsIterative (5, GenerateSOurceData (5), Сумм, 60) Прошедшее: 00: 00: 00,0013067 puzzle.Solve (5, 60, PuzzleOnSubsetFound) Прошедшее: 00: 00: 21,3520840