Backtracking – Subset sum with C#
Here’s an example of backtracking algorithm implemented in C#.
This solves the Subset sum
Subset sum problem is NP-complete and depending on your data set the running time can be very slow.
program.cs
using System; using System.Collections.Generic; using System.Diagnostics; using System.Globalization; using System.Linq; using System.Threading; /// <summary> /// Author: Kunuk Nykjaer /// Backtracking Algorithm in C# /// Subset sum /// /// With list numbers and a given sum value /// Find subset of list which adds up to the given sum value. /// </summary> public class Program { static readonly Action<object> Write = Console.Write; static readonly Func<ConsoleKeyInfo> ReadKey = Console.ReadKey; // Composition root static void Main(string[] args) { Thread.CurrentThread.CurrentCulture = CultureInfo.GetCultureInfo("en-US"); // Use timer for checking algo time var sw = new Stopwatch(); sw.Start(); // ----------------------------------------- // ** INSERT YOUR DATA HERE ** // Init config, var config = new Config { MaxSolutions = 1, // restrict result count ShowProgress = true, // show backtrack progress ShowStatus = true, // show iteration progress DisplaySolutions = true, // Show solution list DetectCodeError = false, // slower running time if true }; // set var set = new List<float> { -7, -3, -2, 5, 8 }; // subset sum var sum = 0; // ** END INSERT DATA ** // ----------------------------------------- // Init data var P = new Data(set, sum, config); // Init backtrack algo var bt = new Backtrack(Write, P); // Find solutions bt.Run(); // Algo done, stop time sw.Stop(); // Show results bt.Show(); Write(string.Format("\nSec: {0}\nPress a key to exit\n", sw.ElapsedMilliseconds / 1000d)); ReadKey(); } } class Config { public int MaxSolutions { get; set; } public bool ShowProgress { get; set; } public bool ShowStatus { get; set; } public bool DisplaySolutions { get; set; } public bool DetectCodeError { get; set; } public Config() { MaxSolutions = 1; } } class Backtrack { readonly Action<object> _write; private readonly Data _p; private bool _maxSolutionsReachedExitBt; public Backtrack(Action<object> write, Data P) { _write = write; _p = P; } void UndoUpdate(Data P, Candidate c, int depth) { P.Remove(c); if (P.Config.ShowProgress) { Print(P, c, depth); } } void Update(Data P, Candidate c, int depth) { P.Add(c); if (P.Config.ShowProgress) { Print(P, c, depth); } } /* wikipedia: http://en.wikipedia.org/wiki/Backtracking procedure bt(P,c) if reject(P,c) then return update(P,c) // update data if accept(P,c) then output(P,c) s ← first(P,c) while s ≠ Λ do bt(P,s) s ← next(P,s) end while undoUpdate(P,c) // backtracking starts here end procedure */ // O(?) void Bt(Data P, Candidate c, int depth) { if (Reject(P, c)) { return; } // Update data Update(P, c, depth); if (P.Config.ShowStatus) { ShowStatus(P, c); } // print status if (Accept(P, c)) { SaveResult(P, c); } if (_maxSolutionsReachedExitBt) { return; } // custom exit var s = First(P, c); while (s != null) { Bt(P, s, depth + 1); s = Next(P, s); } if (_maxSolutionsReachedExitBt) { return; } // custom exit // Leaf, dead end, backtrack, roll back data UndoUpdate(P, c, depth); } // O(1) bool Accept(Data P, Candidate c) { const float epsilon = 0.000001f; if (Math.Abs(P.Sum - P.WorkingSum) < epsilon) { return true; } return false; } // O(1) bool Reject(Data P, Candidate c) { if (_maxSolutionsReachedExitBt) { return true; } if (c == null) { throw new ArgumentNullException("c"); } var i = P.Numbers[c.Index]; // Optimization vs. iterate all combinations // Reject if rest of sorted list contains positive numbers if (i >= 0 && i + P.WorkingSum > P.Sum){ return true; } return false; } public void Run() { var setsum = _p.Numbers.Sum(); if (_p.Sum > setsum) { _write(string.Format("Sum: {0} is bigger than set sum {1}, no solutions exists\n", _p.Sum, setsum)); return; } for (int i = 0; i < _p.Numbers.Length; i++) { Bt(_p, new Candidate { Index = i }, 1); } } public void Show() { _write(string.Format("Max solutions: {0}\n", _p.Config.MaxSolutions)); _write(string.Format("Sum: {0}\n", _p.Sum)); _write(string.Format("Set:\n")); _p.Numbers.ToList().ForEach(a => _write(a + ", ")); if (_p.Config.DisplaySolutions) { _write(string.Format("\n\n*** Solutions:\n\n")); _p.SolutionsList.ForEach(_write); } _write(string.Format("\nUnique Paths Tried: {0}\n", _p.PathsTried)); _write(string.Format("Solutions count: {0}\n", _p.Solutions)); } // O(n) where n is path length void SaveResult(Data P, Candidate c) { P.Solutions++; if (P.Config.DisplaySolutions) { // Only save result data if to be displayed var list = P.Stack.ToList(); list.Reverse(); string numbers = list.Aggregate("", (a, b) => a + (P.Numbers[b] + ", ")); string indexes = list.Aggregate("", (a, b) => a + (b + ", ")); P.SolutionsList.Add(string.Format("Numbers: {0}\nIndexes: {1}\n\n", numbers, indexes)); } if (P.Solutions >= P.Config.MaxSolutions) { _maxSolutionsReachedExitBt = true; } } // First valid child from path // O(1) Candidate First(Data P, Candidate c) { int j = c.Index + 1; if (j >= P.Numbers.Length) { return null; } return new Candidate { Index = j }; } // Next sibling from current leaf // O(1) Candidate Next(Data P, Candidate c) { int j = c.Index + 1; if (j >= P.Numbers.Length) { return null; } return new Candidate { Index = j }; } void Print(Data P, Candidate c, int depth) { _write(string.Format("path: {0} \tsum: {1} \tdepth: {2}\n", P.Path.Get(), P.WorkingSum, depth)); } void ShowStatus(Data P, Candidate c) { // Debug if (P.PathsTried % 500000 == 0) { _write(string.Format("Paths tried: {0:n0} \tSolutions: {1} \tPath: {2}\n", P.PathsTried, P.Solutions, P.Path.Get())); } } } class Candidate { public int Index { get; set; } public override string ToString() { return string.Format("{0}", Index); } } class Data { // Init data public Config Config; public float Sum { get; private set; } public float[] Numbers { get; private set; } // Backtracking data public bool[] Path { get; private set; } public float WorkingSum { get; private set; } public Stack<int> Stack = new Stack<int>(); // Result data public int PathsTried; public List<string> SolutionsList = new List<string>(); public int Solutions { get; set; } // Only used for Detect code error public HashSet<string> SetPathsTried = new HashSet<string>(); public Data(List<float> numbers, float sum, Config config) { numbers.Sort(); // sort is used for reject condition in bt algo Numbers = numbers.ToArray(); Path = new bool[Numbers.Length]; Sum = sum; Config = config; } // O(1) public void Remove(Candidate c) { if (c == null) { throw new ArgumentNullException("c"); } var i = Stack.Pop(); UpdatePath(false, i); WorkingSum -= Numbers[i]; } // O(1) (or O(n) if detectCodeError) public void Add(Candidate c) { if (c == null) { throw new ArgumentNullException("c"); } UpdatePath(true, c.Index); WorkingSum += Numbers[c.Index]; Stack.Push(c.Index); PathsTried++; if (Config.DetectCodeError) { var path = Stack.GetString(); // O(n) where n is stack count if (SetPathsTried.Contains(path)) // O(1) { throw new ApplicationException(string.Format("Path already visited: {0}", path)); } SetPathsTried.Add(path); } } // O(1) void UpdatePath(bool value, int index) { if (Path[index] == value) { throw new ApplicationException(string.Format("Path already set for index: {0}, value: {1}", index, Numbers[index])); } Path[index] = value; } } static class Extensions { public static string GetString<T>(this IEnumerable<T> arr) { return arr.Aggregate("", (a, b) => a + string.Format("{0}->", b)); } public static string Get(this IEnumerable<bool> arr) { return arr.Aggregate("", (a, b) => a + (b ? "1" : "0")); } }
Examples of usage and results
Set including negative numbers
Find subset sum from set with negative and positive numbers.
Configuration is set as:
– MaxSolutions = 3,
– ShowProgress = false,
– ShowStatus = true,
– DisplaySolutions = true
Max solutions: 3 Sum: 100 Set: -10, -1, 1, 2, 5, 10, 20, 20, 30, 40, 50, *** Solutions: Numbers: -10, -1, 1, 10, 20, 30, 50, Indexes: 0, 1, 2, 5, 6, 8, 10, Numbers: -10, -1, 1, 10, 20, 30, 50, Indexes: 0, 1, 2, 5, 7, 8, 10, Numbers: -10, -1, 1, 20, 20, 30, 40, Indexes: 0, 1, 2, 6, 7, 8, 9, Unique Paths Tried: 162 Solutions count: 3 Sec: 0.007
Solutions count only
Here we are interested of numbers of subset sum matching the sum value.
Configuration is set as:
– MaxSolutions = int.MaxValue,
– ShowProgress = false,
– ShowStatus = true,
– DisplaySolutions = false
Paths tried: 500.000 Solutions: 14810 Path: 110111010011000000110000000 Paths tried: 1.000.000 Solutions: 28743 Path: 101111011001111010011000000 Paths tried: 1.500.000 Solutions: 42862 Path: 100111010101001000001000000 Paths tried: 2.000.000 Solutions: 56129 Path: 100000000000000101110100000 Paths tried: 2.500.000 Solutions: 70302 Path: 010111110101101001100000000 Paths tried: 3.000.000 Solutions: 83851 Path: 010000010100111010010010000 Paths tried: 3.500.000 Solutions: 97535 Path: 001000100111100010000000000 Paths tried: 4.000.000 Solutions: 110731 Path: 000001011010011000111000000 Max solutions: 2147483647 Sum: 500 Set: 10, 10, 15, 15, 20, 20, 25, 25, 30, 30, 35, 35, 40, 40, 45, 45, 50, 50, 55, 60, 65, 100, 200, 300, 400, 500, 600, Unique Paths Tried: 4114568 Solutions count: 113508 Sec: 3.639
Floating numbers
Max solutions: 5 Sum: 3 Set: -1, 0.1, 0.2, 0.5, 1, 1.5, 2, 2.5, 2.9, *** Solutions: Numbers: -1, 0.1, 1, 2.9, Indexes: 0, 1, 4, 8, Numbers: -1, 0.5, 1, 2.5, Indexes: 0, 3, 4, 7, Numbers: -1, 0.5, 1.5, 2, Indexes: 0, 3, 5, 6, Numbers: -1, 1.5, 2.5, Indexes: 0, 5, 7, Numbers: 0.1, 2.9, Indexes: 1, 8, Unique Paths Tried: 98 Solutions count: 5
Advertisements
Very elegant and fast algorithm, thanks very much. With under 20 elements in the dataset, it is very quick to find solutions. I was working with Decimal type, so I figured I could lose the epsilon value too. Thanks.
hiblet
May 3, 2017 at 1:12 pm