Math Is Fun Forum

Hi,

I have some performance / efficiency related questions for you. It is related to your blog post here:

http://www.mathsisfun.com/combinatorics/combinations-permutations.html

Here is the scenario:

An input file contains integers which can be positive and negative and may contain duplicate values. Each line has one record / integer. We want to compute the number of x values within the range -10000 ≤ x ≤ 10000 such that there are distinct numbers a, b where a + b = x.

For example, consider the following data:

-10001
1
2
-10001
1
5
-2
9999
10000

I have some VBA code which successfully determines the number of unique values in the calculated range after pasting the values into an Excel spreadsheet:
Sub Adder()
   
    Dim rngCell As Excel.Range
    Dim rngRange As Excel.Range
   
    Dim colNumbers As Collection
    Dim colNumbersUnique As Collection
   
    Dim lngRows As Long
    Dim lngRowsInner As Long
    Dim lngAdd As Long
   
    On Error GoTo ErrorHandler
   
    Set rngRange = Selection
    Set colNumbersUnique = New Collection
    Set colNumbers = New Collection
   
    For lngRows = 1 To rngRange.Rows.Count
        colNumbersUnique.Add rngRange.Cells(lngRows, 1).Value, CStr(rngRange.Cells(lngRows, 1).Value)
    Next lngRows
   
    For lngRows = 1 To colNumbersUnique.Count - 1
        For lngRowsInner = lngRows + 1 To colNumbersUnique.Count
       
        lngAdd = colNumbersUnique.Item(lngRows) + colNumbersUnique.Item(lngRowsInner)
       
        If lngAdd >= -10000 And lngAdd <= 10000 Then
            colNumbers.Add lngAdd, CStr(lngAdd)
        End If
               
        Next lngRowsInner
    Next lngRows
   
    Debug.Print colNumbers.Count
   
ErrorHandler:
   
    Select Case Err.Number
        Case 457 ' Runtime Error 457: This key is already associated with an element of this collection
            'Ignore this error as it is expected when retrieving unique values via a collection
            Resume Next
        Case Else
            MsgBox Err.Number & ": " & Err.Description
    End Select
   
End Sub

The answer for the range provided would be 12 unique values subsequent to calculation performed by the nested the loops. However, the above is not so efficient when tested against a large set of values.

Consequently, I have the following questions:

There are algorithms and even Excel formulas to determine the number of possible combinations (i.e. COMBIN in Excel, for example). However, what about unique values in a series subsequent to some form of combination?

The above VBA sample applies the calculation manually over the course of looping. I would think that there may be some form of algorithm that I'm just not quite seeing. Code answers may be better served in .Net such as C#, etc. For example, I tried something like this:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Data.OleDb;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

            string filePath;
            filePath = "[Insert file name here or use FileOpen dialog]";

            if (filePath.Length > 0)
            {
                // Grab all of the numbers at once
                string[] records = File.ReadAllLines(filePath);
                // Remove all of the duplicates at once
                records = records.Distinct().ToArray();
                // Convert the entire array to integers
                int[] intRecords = Array.ConvertAll<string, int>(records, Convert.ToInt32);

                // Calculate the new list
                var cartesianList = intRecords.SelectMany(a => intRecords.Select(b => a + b));
                //var countResults = cartesianList.TakeWhile(items => items <= -10000 && items >= 10000);
                cartesianList = cartesianList.Distinct();
                // Select the values which are between -10,000 and 10,000
                var countResults = from vals in cartesianList
                                   where vals <= 10000 &&
                                    vals >= -10000
                                   select vals;
                countResults = countResults.Distinct();             
                MessageBox.Show(countResults.Count().ToString());
            }

However, I am not getting the correct result count. I'm getting a number greater than expected. Further, the TakeWhile statement, which is commented out, is not returning anything.

Your thoughts?

Thanks,

-- Todd