topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • July 22, 2018, 01:38 PM
  • Proudly celebrating 13 years online.
  • Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.
  • donate

Author Topic: How can I find approximate matches of numbers?  (Read 526 times)

kalos

  • Member
  • Joined in 2006
  • **
  • default avatar
  • Posts: 1,615
    • View Profile
    • Donate to Member
How can I find approximate matches of numbers?
« on: July 12, 2018, 10:45 AM »
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

  • Supporting Member
  • Joined in 2006
  • **
  • Posts: 3,193
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #1 on: July 12, 2018, 02:06 PM »
Do you have a set of example lists? And point out how you'd like things to match/group?

KodeZwerg

  • Member
  • Joined in 2018
  • **
  • Posts: 95
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #2 on: July 12, 2018, 07:51 PM »
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 [Select]
  1. procedure TForm148.Button2Click(Sender: TObject);
  2. type
  3.   TIntArray = array of Integer;
  4.  
  5.   procedure CountOccurrences(const List1, List2: TStrings; var Result: TIntArray);
  6.   var
  7.     i, CurIndex: Integer;
  8.   begin
  9.     for i := 0 to List2.Count - 1 do
  10.     begin
  11.       CurIndex := List1.IndexOf(List2[i]);
  12.       if CurIndex >= 0 then
  13.         Result[CurIndex] := Succ(Result[CurIndex]);
  14.     end;
  15.   end;
  16.  
  17. var
  18.   TempList: TIntArray;
  19.   i: Integer;
  20. begin
  21.   SetLength(TempList, ListBox1.Items.Count);
  22.   CountOccurrences(ListBox1.Items, ListBox2.Items, TempList);
  23.   for i := Low(TempList) to High(TempList) do
  24.     ShowMessage(ListBox1.Items[i] + ': ' + IntToStr(TempList[i]));
  25.   SetLength(TempList, 0);
  26. end;

wraith808

  • Supporting Member
  • Joined in 2006
  • **
  • default avatar
  • Posts: 9,555
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #3 on: July 12, 2018, 11:34 PM »
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

  • Supporting Member
  • Joined in 2007
  • **
  • Posts: 415
  • Beer, beer, beer, I'm going for a beer!
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #4 on: July 13, 2018, 03:53 AM »
Code: C# [Select]
  1. class Program
  2.     {
  3.         static void Main(string[] args)
  4.         {
  5.             List<float> A = new List<float> {};
  6.             List<float> B = new List<float> {};
  7.  
  8.             FillListWithRandNumbers(A, 20);
  9.             FillListWithRandNumbers(B, 20);
  10.  
  11.             var approximateNumbers = ApproxNumbers(A, B, 0.05f);
  12.  
  13.  
  14.             Console.WriteLine("List A: ");
  15.             foreach (var num in A)
  16.             {
  17.                 Console.WriteLine(num);
  18.             }
  19.             Console.WriteLine();
  20.  
  21.             Console.WriteLine("List B: ");
  22.             foreach (var num in B)
  23.             {
  24.                 Console.WriteLine(num);
  25.             }
  26.             Console.WriteLine();
  27.  
  28.             Console.WriteLine("Numbers within 5% of numbers in list A");
  29.             foreach (var tup in approximateNumbers)
  30.             {
  31.                 Console.WriteLine(tup.Item1 + " " + tup.Item2);
  32.             }
  33.  
  34.             Console.WriteLine("Match amount: " + approximateNumbers.Count);
  35.  
  36.         }
  37.  
  38.         static void FillListWithRandNumbers(List<float> list, int amount = 100)
  39.         {
  40.             Random r = new Random(DateTime.Now.Millisecond);
  41.             int range = 100;
  42.             for (var i = 0; i < amount; ++i)
  43.             {
  44.                 list.Add((float)r.NextDouble() * range);
  45.             }
  46.         }
  47.  
  48.         static List<Tuple<float, float>> ApproxNumbers(List<float> a, List<float> b, float tolerance)
  49.         {
  50.             List<Tuple<float, float>> ret = new List<Tuple<float, float>>();
  51.  
  52.             foreach (var num1 in a)
  53.             {
  54.                 foreach (var num2 in b)
  55.                 {
  56.                     if (Math.Abs(num1 - num2) < num1 * tolerance)
  57.                     {
  58.                         ret.Add(new Tuple<float, float>(num1, num2));
  59.                     }
  60.                 }
  61.             }
  62.  
  63.             return ret;
  64.         }
  65.     }


Something like this?
Stop mousering people so much - Mouser

KodeZwerg

  • Member
  • Joined in 2018
  • **
  • Posts: 95
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #5 on: July 13, 2018, 03:54 AM »
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.
- 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
- 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
- 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)
« Last Edit: July 13, 2018, 04:38 AM by KodeZwerg »

4wd

  • Supporting Member
  • Joined in 2006
  • **
  • Posts: 4,885
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #6 on: July 14, 2018, 06:12 AM »
Code: PowerShell [Select]
  1. # Remove test files
  2. Remove-Item .\TestList?.txt
  3. # Generate two files containing unique random numbers for comparison
  4. 1..100 | % {Get-Random -Minimum 95 -Maximum 200 } | Sort -Unique | Out-File .\TestList1.txt -Append
  5. 1..100 | % {Get-Random -Minimum 95 -Maximum 200 } | Sort -Unique | Out-File .\TestList2.txt -Append
  6.  
  7. # Read the files into an object (array)
  8. $list1 = Get-Content .\TestList1.txt
  9. $list2 = Get-Content .\TestList2.txt
  10.  
  11. # Initialise match count
  12. $total = 0
  13.  
  14. # For each value in list 1 loop through every value in list 2
  15. for ($i = 0; $i -lt $list1.Count; $i++) {
  16.   for ($j = 0; $j -lt $list2.Count; $j++) {
  17.     $tmp = $list2[$j]/1                                                                  # Simple conversion of string to number
  18.     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
  19.       $total++                                                                           # Increment match count if a match
  20.       $out = 'Match ' + $total.ToString() + ': ' + $list1[$i] + ' ±5% -> ' + $list2[$j]  # Format output
  21.       Write-Host $out                                                                    # Write to console
  22.       Out-File  .\TestList3.txt -InputObject $out -Append                                # Write to file
  23.     }
  24.   }                                                                                      # Round we go again
  25. }                                                                                        # ... and again
  26.  
  27. # The End
« Last Edit: July 14, 2018, 06:26 AM by 4wd »

wraith808

  • Supporting Member
  • Joined in 2006
  • **
  • default avatar
  • Posts: 9,555
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #7 on: July 14, 2018, 11:19 AM »
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

  • Member
  • Joined in 2018
  • **
  • Posts: 95
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #8 on: July 14, 2018, 04:13 PM »
In my proto-Code i was wrong anyway  :o
What i've called BigList should be infact the smaller List = fastest performance.
And the "Result :=" Lines should be removed from all Procedures ^_^

4wd

  • Supporting Member
  • Joined in 2006
  • **
  • Posts: 4,885
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #9 on: July 14, 2018, 08:05 PM »
I still maintain that the problem hasn't been defined properly, so they could be for naught

That is always the case.

Target

  • Honorary Member
  • Joined in 2006
  • **
  • Posts: 1,678
    • View Profile
    • Donate to Member
Re: How can I find approximate matches of numbers?
« Reply #10 on: July 15, 2018, 02:43 AM »
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?