Lookup algorithm

  • Thread starter Thread starter Martin Hart Turner
  • Start date Start date
M

Martin Hart Turner

Hi:

I am looking for a 'best-fit' algorithm for a (small) list of numbers. Allow
me to explain.

Imagine I have a list is integers as so: 1, 2, 3, 1, 5, 8, 1, 12, 2, 1. You
can see there are repeats in the list.

Given another integer number, I want to know which numbers from the list,
when summed, give me the requested value. For instance, if I want to find
which numbers make the sum of 7, the algorithm could return 1+2+3+1 or 5+2
or 2+3+2. Returning an array of integers that point to the candidates in the
list would suffice as the return value, for instance in the previous example
I would get [0,1,2,3] or [4,1] or [1,2,8]. I only need one sequence
returned, not all possible combinations. Ideally, the solution would be the
shortest route e.g. the combination with the least number of elements in the
returned array (of list).

Can anyone give me some pointers as to how I might go about this task?

TIA,
Martin.
 
Hi:

I am looking for a 'best-fit' algorithm for a (small) list of numbers.
Allow me to explain.

Imagine I have a list is integers as so: 1, 2, 3, 1, 5, 8, 1, 12, 2, 1.
You can see there are repeats in the list.

Given another integer number, I want to know which numbers from the list,
when summed, give me the requested value. For instance, if I want to find
which numbers make the sum of 7, the algorithm could return 1+2+3+1 or 5+2
or 2+3+2. Returning an array of integers that point to the candidates in
the list would suffice as the return value, for instance in the previous
example I would get [0,1,2,3] or [4,1] or [1,2,8]. I only need one
sequence returned, not all possible combinations. Ideally, the solution
would be the shortest route e.g. the combination with the least number of
elements in the returned array (of list).

Can anyone give me some pointers as to how I might go about this task?

TIA,
Martin.
Click to expand...

Google for 'solve countdown numbers' - most hits will be complete programs
but there is source available for one - written in 'd' but it looks quite
like 'c'.
 
Martin Hart Turner said:
Hi:

I am looking for a 'best-fit' algorithm for a (small) list of numbers. Allow
me to explain.

Imagine I have a list is integers as so: 1, 2, 3, 1, 5, 8, 1, 12, 2, 1. You
can see there are repeats in the list.

Given another integer number, I want to know which numbers from the list,
when summed, give me the requested value. For instance, if I want to find
which numbers make the sum of 7, the algorithm could return 1+2+3+1 or 5+2
or 2+3+2. Returning an array of integers that point to the candidates in the
list would suffice as the return value, for instance in the previous example
I would get [0,1,2,3] or [4,1] or [1,2,8]. I only need one sequence
returned, not all possible combinations. Ideally, the solution would be the
shortest route e.g. the combination with the least number of elements in the
returned array (of list).

Can anyone give me some pointers as to how I might go about this task?

TIA,
Martin.
Click to expand...

basic algorithm:

List<int> FindItems(List<int> values, int target)
{
// 1. if target is 0, return null list
// 2. if values are empty, return null list
// 3. find single item that matches target, return list of that value.
// 4. otherwise, pick any value
// 4.a. remove value from list
// 4.b. recurse using new list, and target less value removed.
}

If the list returned is null, you failed, otherwise, you have the list of
values. Just find their indicies in the original list.

Mike
 
Mike:

I thought your idea was very simple and to the point, so I wrote my
algorithm based on your pointers.

Below is the code I came up with, thanks for your time.

Regards,
Martin.

Code: 
using System;
using System.Collections.Generic;
using System.Linq;

namespace OptimumAlgorithm
{
internal class Program
{
private static void Main(string[] args)
{
//                                       1  2  3  4  5  6  7  8   9
10
List<int> candidates = new List<int>() { 1, 2, 3, 1, 5, 8, 1, 12, 2,
1 };
//                                       1   2  3  4  5  6  7  8  9
10
//                    Descending order:  12, 8, 5, 3, 2, 2, 1, 1, 1, 1
candidates.Sort((lhs, rhs) =>
System.Collections.Generic.Comparer<int>.Default.Compare(rhs, lhs));
for(int target = 1; target < 40; target++)
{
List<int> usedValues = new List<int>();
List<int> results = findOptimum(candidates, target, usedValues);
if(results != null && results.Count > 0)
System.Console.WriteLine(string.Format("Target value={0},
found:{1}", target, getDescTree(usedValues)));
else
System.Console.WriteLine("No results");
}
System.Console.ReadLine();
}

private static List<int> findOptimum(List<int> candidates, int target,
List<int> usedValues)
{
if(target != 0 && candidates.Count > 0)
{
int result = (from item in candidates where item == target select
item).FirstOrDefault();
if(result != 0)
{
usedValues.Add(target);
return new List<int>() { result };
}
var validValues = (from item in candidates where item < target
select item).ToList();
if(validValues != null && validValues.Count > 1)
{
int removedValue = validValues[0];
validValues.RemoveAt(0);
usedValues.Add(removedValue);
return findOptimum(new List<int>(validValues), target -
removedValue, usedValues);
}
}
return null;
}

private static string getDescTree(List<int> path)
{
System.Text.StringBuilder sb = new System.Text.StringBuilder();
sb.AppendFormat("suma={0} (", path.Sum());
bool isFirst = true;
foreach(int item in path)
{
sb.AppendFormat("{0}{1}", (isFirst) ? string.Empty : ", ", item);
isFirst = false;
}
sb.Append(")");
return sb.ToString();
}
}
}

"Family Tree Mike" <[email protected]> escribió en el
mensaje de noticias
Martin Hart Turner said:
Hi:

I am looking for a 'best-fit' algorithm for a (small) list of numbers.
Allow
me to explain.

Imagine I have a list is integers as so: 1, 2, 3, 1, 5, 8, 1, 12, 2, 1.
You
can see there are repeats in the list.

Given another integer number, I want to know which numbers from the list,
when summed, give me the requested value. For instance, if I want to find
which numbers make the sum of 7, the algorithm could return 1+2+3+1 or
5+2
or 2+3+2. Returning an array of integers that point to the candidates in
the
list would suffice as the return value, for instance in the previous
example
I would get [0,1,2,3] or [4,1] or [1,2,8]. I only need one sequence
returned, not all possible combinations. Ideally, the solution would be
the
shortest route e.g. the combination with the least number of elements in
the
returned array (of list).

Can anyone give me some pointers as to how I might go about this task?

TIA,
Martin.
Click to expand...

basic algorithm:

List<int> FindItems(List<int> values, int target)
{
// 1. if target is 0, return null list
// 2. if values are empty, return null list
// 3. find single item that matches target, return list of that value.
// 4. otherwise, pick any value
// 4.a. remove value from list
// 4.b. recurse using new list, and target less value removed.
}

If the list returned is null, you failed, otherwise, you have the list of
values. Just find their indicies in the original list.

Mike
Click to expand...
 
Back
Top