Monday, October 28, 2013

Combination Algorithm

I am trying to write a small code to find the possible combinations from a list of integer values which when added is equal to the input value or somewhat nearing.


List<int> comb = new List<comb>() { 618, 350, 308, 300, 250, 232, 200, 128 };


The above list contains the integer values from which the proper combination has to be generated


The combination should have least number of values i.e., greatest number has to used most


Example:


If Input from User [Value = 2386]


Combination 1 = 618 + 350 + 308 + 300 + 250 + 232 + 200 + 128


Combination 2 = 618 + 618 + 618 + 300 + 232


I have used the below code, but have missed some logic.



public static void Main(string[] args)
{
//subtotal list
List<int> totals = new List<int>(new int[] { 618, 350, 308, 300, 250, 232, 200, 128 });

// get matches
List<int[]> results = KnapSack.MatchTotal(2682, totals);

// print results
foreach (var result in results)
{
Console.WriteLine(string.Join(",", result));
}

Console.WriteLine("Done.");
}

internal static List<int[]> MatchTotal(int theTotal, List<int> subTotals)
{
List<int[]> results = new List<int[]>();
while (subTotals.Contains(theTotal))
{
results.Add(new int[1] { theTotal });
subTotals.Remove(theTotal);
}

if (subTotals.Count == 0)
return results;

subTotals.Sort();

double mostNegativeNumber = subTotals[0];
if (mostNegativeNumber > 0)
mostNegativeNumber = 0;

if (mostNegativeNumber == 0)
subTotals.RemoveAll(d => d > theTotal);

for (int choose = 0; choose <= subTotals.Count; choose++)
{
IEnumerable<IEnumerable<int>> combos = Combination.Combinations(subTotals.AsEnumerable(), choose);

results.AddRange(from combo in combos where combo.Sum() == theTotal select combo.ToArray());
}
return results;
}


public static class Combination
{
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int choose)
{
return choose == 0 ?
new[] { new T[0] } :
elements.SelectMany((element, i) =>
elements.Skip(i + 1).Combinations(choose - 1).Select(combo => (new[] { element }).Concat(combo)));
}
}

Is there any other way other than the above to get combinations


No comments:

Post a Comment