How can I find approximate matches of numbers?

[kalos]

Hello!

I have two lists with numbers. How can I find how many pairs there are between those two lists (ie similarity), where each pair is the number from second list that matches +/-5% to a number in the first list?

Thanks!

[Ath]

Do you have a set of example lists? And point out how you'd like things to match/group?

[KodeZwerg]

I dont know if i understood correct, if you want to know index positions of same values, heres a Delphi Snippet that does such, hope it helps.

Code: (delphi)

procedure TForm148.Button2Click(Sender: TObject);
type
  TIntArray = array of Integer;

  procedure CountOccurrences(const List1, List2: TStrings; var Result: TIntArray);
  var
    i, CurIndex: Integer;
  begin
    for i := 0 to List2.Count - 1 do
    begin
      CurIndex := List1.IndexOf(List2[i]);
      if CurIndex >= 0 then
        Result[CurIndex] := Succ(Result[CurIndex]);
    end;
  end;

var
  TempList: TIntArray;
  i: Integer;
begin
  SetLength(TempList, ListBox1.Items.Count);
  CountOccurrences(ListBox1.Items, ListBox2.Items, TempList);
  for i := Low(TempList) to High(TempList) do
    ShowMessage(ListBox1.Items[i] + ': ' + IntToStr(TempList[i]));
  SetLength(TempList, 0);
end;

[wraith808]

Well, he wants to throw in a %match, so that wouldn't do it. 

There's also the matter of what kinds of numbers are in the lists.  And whether he wants individual matches, i.e. if you have 95 in one list and 100 and 105 in the other, would it be able to be 2 pairs?  Or only match the first one?  And if one is matches in the second list, is it gone for matches?

The spec for this is pretty non-specific. 

[p3lb0x]

Code: ( csharp)

    class Program
    {
        static void Main(string[] args)
        {
            List<float> A = new List<float> {};
            List<float> B = new List<float> {};

            FillListWithRandNumbers(A, 20);
            FillListWithRandNumbers(B, 20);

            var approximateNumbers = ApproxNumbers(A, B, 0.05f);


            Console.WriteLine("List A: ");
            foreach (var num in A)
            {
                Console.WriteLine(num);
            }
            Console.WriteLine();

            Console.WriteLine("List B: ");
            foreach (var num in B)
            {
                Console.WriteLine(num);
            }
            Console.WriteLine();

            Console.WriteLine("Numbers within 5% of numbers in list A");
            foreach (var tup in approximateNumbers)
            {
                Console.WriteLine(tup.Item1 + " " + tup.Item2);
            }

            Console.WriteLine("Match amount: " + approximateNumbers.Count);

        }

        static void FillListWithRandNumbers(List<float> list, int amount = 100)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            int range = 100;
            for (var i = 0; i < amount; ++i)
            {
                list.Add((float)r.NextDouble() * range);
            }
        }

        static List<Tuple<float, float>> ApproxNumbers(List<float> a, List<float> b, float tolerance)
        {
            List<Tuple<float, float>> ret = new List<Tuple<float, float>>();

            foreach (var num1 in a)
            {
                foreach (var num2 in b)
                {
                    if (Math.Abs(num1 - num2) < num1 * tolerance)
                    {
                        ret.Add(new Tuple<float, float>(num1, num2));
                    }
                }
            }

            return ret;
        }
    }

Something like this?

[KodeZwerg]

Well, he wants to throw in a %match, so that wouldn't do it.

Now i've understood, thank you for explaining to me!
Here is theory on how to do that, simple range check.

Code

 - checker code
   function IsInRange(MinValue, MaxValue: double): Boolean;
   var
     Count: Integer;
   begin
     Result := False;
     for count := 0 to BigList.NumberOfItems -1 do
       if ((BigList.Items[Count].Value >= MinValue) or (BigList.Items[Count].Value <= MaxValue)) then
       begin
         Result := True;
         Exit;
       end;     
   end;

 - maincode
   for Count := 0 to Masterlist.NumberOfItems -1 do
   begin
     MinValue := Calculate( MasterList.Items[Count].Value -5% )
     MaxValue := Calculate( MasterList.Items[Count].Value +5% )
     if IsInRange(MinValue, MaxValue) then
       CompareListResults.AddNewItem := Count;
   end;

In that sample the MasterList should be the List with less Items than BigList.
I hope you now get an Idea on how to solve this.

Since its just proto-code, it give only first match from criteria MinValue and MaxValue back.

Edited this way it will grab all Matches from BigList

Code

 - checker code
   procedure SaveRanges(MinValue, MaxValue: double; var SavedList: TList);
   var
     Count: Integer;
   begin
     Result := False;
     for count := 0 to BigList.NumberOfItems -1 do
       if ((BigList.Items[Count].Value >= MinValue) or (BigList.Items[Count].Value <= MaxValue)) then
         SavedList.Items.Add( IntToStr(Count) );
   end;

 - maincode
   NewList := TList.Create();
   for Count := 0 to Masterlist.NumberOfItems -1 do
   begin
     MinValue := Calculate( MasterList.Items[Count].Value -5% )
     MaxValue := Calculate( MasterList.Items[Count].Value +5% )
     SaveRanges(MinValue, MaxValue, NewList);
   end;

This sample would hold all matches in NewList.


Edited this way it will grab all Matches from BigList and Save callers Index within

Code

 - checker code
   procedure SaveRanges(const MinValue: double; const MaxValue: double; const CallerIndex: Integer; var SavedList: TList);
   var
     Count: Integer;
   begin
     Result := False;
     for count := 0 to BigList.NumberOfItems -1 do
       if ((BigList.Items[Count].Value >= MinValue) or (BigList.Items[Count].Value <= MaxValue)) then
         SavedList.Items.Add( IntToStr(CallerIndex) + ' found match with ' + IntToStr(Count) );
   end;

 - maincode
   NewList := TList.Create();
   for Count := 0 to Masterlist.NumberOfItems -1 do
   begin
     MinValue := Calculate( MasterList.Items[Count].Value -5% )
     MaxValue := Calculate( MasterList.Items[Count].Value +5% )
     SaveRanges(MinValue, MaxValue, Count, NewList);
   end;

This sample would hold all matches in NewList, ready to use with matches display.

Ps: If you are confused of line "for Count := 0 to Masterlist.NumberOfItems -1 do", adjust this to your Language.
In Delphi Lists Index begin at "0" and NumberOfItems at "1". NumberOfItems "0" would mean Index "-1" (no item exist in List)

[4wd]

Code: ( powershell)

# Remove test files
Remove-Item .\TestList?.txt
# Generate two files containing unique random numbers for comparison
1..100 | % {Get-Random -Minimum 95 -Maximum 200 } | Sort -Unique | Out-File .\TestList1.txt -Append
1..100 | % {Get-Random -Minimum 95 -Maximum 200 } | Sort -Unique | Out-File .\TestList2.txt -Append

# Read the files into an object (array)
$list1 = Get-Content .\TestList1.txt
$list2 = Get-Content .\TestList2.txt

# Initialise match count
$total = 0

# For each value in list 1 loop through every value in list 2
for ($i = 0; $i -lt $list1.Count; $i++) {
  for ($j = 0; $j -lt $list2.Count; $j++) {
    $tmp = $list2[$j]/1                                                                  # Simple conversion of string to number
    if (($tmp -gt ($list1[$i]/1 * 0.95)) -and ($tmp -lt ($list1[$i]/1 * 1.05))) {        # Compare value from list 2 to within 5% of value from list 1
      $total++                                                                           # Increment match count if a match
      $out = 'Match ' + $total.ToString() + ': ' + $list1[$i] + ' ±5% -> ' + $list2[$j]  # Format output
      Write-Host $out                                                                    # Write to console
      Out-File  .\TestList3.txt -InputObject $out -Append                                # Write to file
    }
  }                                                                                      # Round we go again
}                                                                                        # ... and again

# The End

[wraith808]

All of these are great solutions.  I still maintain that the problem hasn't been defined properly, so they could be for naught. 

Ath had the right questions in the initial reply. 

[KodeZwerg]

In my proto-Code i was wrong anyway 
What i've called BigList should be infact the smaller List = fastest performance.
And the "Result :=" Lines should be removed from all Procedures ^_^

[4wd]

I still maintain that the problem hasn't been defined properly, so they could be for naught

That is always the case.

[Target]

what happens if there are multiple matches, ie where there are multiple records that fit within that tolerance?

and just how large are these 'numbers', <10 or <100 or >1,000,000 

and how are you 'viewing' these lists?