Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2014-08-03 14:39:07

tmag
Member
Registered: 2014-08-03
Posts: 8

Theoretical Question with Combinations and Permutations

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

Offline

#2 2014-08-03 20:31:25

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Theoretical Question with Combinations and Permutations

Hi;

I am getting 16, please post your 12.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2014-08-04 05:30:02

tmag
Member
Registered: 2014-08-03
Posts: 8

Re: Theoretical Question with Combinations and Permutations

If you run the VBA code against that set of numbers, you will get 12. If you run the .Net, I believe that you will get 16 but, as mentioned, the .Net code is not working as expected.

Thanks

Offline

#4 2014-08-04 06:21:53

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Theoretical Question with Combinations and Permutations

I do not program in VBA or net. I am still getting 16

{-10000, -9999, -9996, -2, -1, 0, 1, 2, 3, 5, 6, 7, 9997, 9998, 9999, 10000}


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2014-08-04 06:53:14

tmag
Member
Registered: 2014-08-03
Posts: 8

Re: Theoretical Question with Combinations and Permutations

You did not remove the duplicate values from the original set. -10,001 and 1. If you sort and remove those dupes prior to calculation, you will get 12. The VBA code automatically removes the dupes when it creates the collection.

Thanks

Offline

#6 2014-08-04 06:58:19

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Theoretical Question with Combinations and Permutations

I did and I am still getting 16.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2014-08-04 07:02:00

tmag
Member
Registered: 2014-08-03
Posts: 8

Re: Theoretical Question with Combinations and Permutations

There are errors in your matrix. For example, what numbers, when added, equal 5 or 2?

Thanks

Offline

#8 2014-08-04 07:07:51

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Theoretical Question with Combinations and Permutations

Hi;

Okay, I am now getting 12. Since this is a permutation I would assume you want a and b to be different and each number in the list used only once?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#9 2014-08-04 09:29:05

tmag
Member
Registered: 2014-08-03
Posts: 8

Re: Theoretical Question with Combinations and Permutations

Correct. a+b, a+c, a+d, and so on, and then b+c, b+d, and so on. From the results, peel away, yet again, any dupes.

What I'm wondering is whether there may be an algorithm which can unravel a pattern? For example, there is the permutation for the number of combinations which is even found in the COMBIN Excel formula. For example, COMBIN(7,2) = 21 wherein out of 7 different numbers there are 21 combinations of 2.

n!/(n-r)!

What I am wondering is if there is a way to determine the number of unique results. That is what I am after. Of course, the mathematical addition vs. string concatenation is wherein lay the deviation from the usual approach.

When one looks at the column of numbers, we immediately know that anything positive added to 10,000 will be outside of the needed results. Similarly with anything negative added to -10,000. We can also look at other numbers within close proximity to those values would not be members of the requested subset depending upon what is added to them. Perhaps a way to avoid looping through all of the numbers is to put them into a hash table wherein the IDs are their values and the loop is adjusted such that only values which would not push the resultant outside of the boundaries would be accepted?

Offline

#10 2014-08-04 10:28:23

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Theoretical Question with Combinations and Permutations

Hi;

How big are lists?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2014-08-04 10:52:44

tmag
Member
Registered: 2014-08-03
Posts: 8

Re: Theoretical Question with Combinations and Permutations

They could be of any size from this small list up to say, 10,000 or a million.

Offline

#12 2014-08-04 12:06:42

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Theoretical Question with Combinations and Permutations

A million! That is a big list especially since the computation is 1000000 x 999999 =  999999000000 possibilities. I am afraid that many is going to slow down any desktop with any language.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#13 2014-08-04 12:39:50

tmag
Member
Registered: 2014-08-03
Posts: 8

Re: Theoretical Question with Combinations and Permutations

Well, we can start with 1000 or 10,000 but that isn't really the issue / question. I think that the real question is wherein lay the optimization? The basic algorithm is not that efficient. If by formulae, one can eliminate large chunks of data, that would greatly speed the process.

Offline

#14 2014-08-04 14:04:49

tmag
Member
Registered: 2014-08-03
Posts: 8

Re: Theoretical Question with Combinations and Permutations

Perhaps a Quick Sort or Counting Sort approach is the ticket here. Instead of comparing whether the value is greater or less than the current value, instead compare whether it is outside of the element range when added to the current value. If so, no longer add values less / greater in regards to their position within the array which should already be sorted.

Any thoughts?

Offline

#15 2014-08-05 01:30:51

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Theoretical Question with Combinations and Permutations

As you suggest, I would sort the list. This way the first time you encounter an a + b that is greater or less you do not do any more.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB