For the math wizards...

[sonny]

This question isnt about any project or db I am working on. Its more about can this be done.

Lets say I had to do the following:

1) I have a range of numbers from 1 - 10
2) I have to preform a task where I can choose any amount of them from that range(no dups)

Lets say I choose 3, 4, 7, 8

3) I then have to take those four numbers and arrange them in sets of 3(no dups)
4) The result has to include every possible way those four numbers can be used in a set of three like below.

3, 4, 7
3, 4, 8
3, 7, 8
4, 7, 8

Now, the result only had to produce what you see above without the need of examining it further. In otherwards; 3, 4, 7 could also be like this:


(3, 4, 7) , (3, 7, 4) , (4, 3, 7) , (4, 7, 3) , (7, 3, 4) , (7, 4, 3)

Is this something that can be done with Access coding?

 

[meboz]

If you choose n-numbers, for 0<n<=10, are you always selecting combinations of (n-1)-numbers?

I havn't given this a hell of a lot of thought but im sure it can be done in vba.

The above question may not matter upon further investigation but you never know...

 

[Jon K]

Combinations Permutations

Lets say I choose 3, 4, 7, 8
.............. used in a set of three like below.
3, 4, 7
3, 4, 8
3, 7, 8
4, 7, 8
..............
Is this something that can be done with Access coding?

To do it purely with VBA code, you will have to follow the Mathematical Model of drawing Combinations of 4 numbers taken 3 at a time.


However, if you put the chosen numbers in a table, you can easily pull the Combinations with a simple query, without having to bother with mathematical modelling.


I have attached a sample database as illustration. You can open the form, choose 4 numbers from the list box and click on the Run Query button to return the Combinations. The code in the On Click event of the command button will place the chosen numbers in the "tblNumbers" table and run the "Combinations" query. The query is flexible in that you can choose even more than 4 numbers.

I have also included a query for pulling the Permutations of the chosen numbers.
.

 

[Mile-O]

Public Function Permutations(intTotal As Integer, intSelected As Integer) As Double
    On Error GoTo Err_Permutations
    If intSelected > intTotal Then Exit Function
    Const LoopEnd As Byte = 0
    Permutations = 1
    Do While intSelected <> LoopEnd
        Permutations = Permutations * (intTotal / intSelected)
        intTotal = intTotal - 1
        intSelected = intSelected - 1
    Loop
    Exit Function
Err_Permutations:
    Permutations = -1
End Function

intTotal is the number you have in total
intSelected is the number you are allowed to select

An example is Britain's National Lottery:

There's 49 numbers but we can only pick six:

So, in the debug window for example

?Permutations(49, 6)

returns:

13,984,816

which is the odds of winning the damn thing.

 

[EMP]

?Permutations(49, 6)

returns:

13,984,816

13,983,816 is the number of Combinations(49, 6).

The number of Permutaions(49, 6) should be 10,068,347,520.


Here are two functions for returning the number of Permutations and Combinations:-

Public Function [b]Permutations[/b](intTotal As Integer, intSelected As Integer)
    Dim Numerator As String
    Dim i As Integer
 
    For i = 0 To intSelected - 1
       Numerator = Numerator & "*" & (intTotal - i)
    Next i
    Permutations = Eval(Mid(Numerator, 2))

End Function

Public Function [b]Combinations[/b](intTotal As Integer, intSelected As Integer)
    Dim Numerator As String
    Dim Denominator As String
    Dim i As Integer
 
    For i = 0 To intSelected - 1
       Numerator = Numerator & "*" & (intTotal - i)
       Denominator = Denominator & "*" & (intSelected - i)
    Next i
    Combinations = Eval(Mid(Numerator, 2) & "/(" & Mid(Denominator, 2) & ")")

End Function

Surely what sonny needs are the actual combinations as displayed by Jon K in his query, not just the total number of combinations.

 

[Mile-O]

Whoops!

 

[The_Doc_Man]

Not that I'm going to sit here and write a ton of code for you, but I will point out that technically this is a problem in recursion. And recursion grows factorially (very quickly.)

To do this in the most general possible case, you are looking at an incredibly complex stack structure (the implication of recursion in VBA) to hold the large number of elements you can generate this way.

It has been done in FORTRAN many times, and you can probably do a web search for PERMUTATIONS. Or you might look up D.E. Knuth's book on The Art of Computer Programming (a three-volume set). I think the volume on sorting and searching might be instructive in this case. But beware - it is a collegiate-level text and gets hairy real fast.

To do this excruciatingly correctly in the general case, where you have an array of M elements and want all the possible combinations and permutations of N elements out of M, you need to pass four items - (1) M, (2) N, (3) the list of M elements, and (4) a partial array of size N.

You need this in three parts, or perhaps three branches.

Branch 1: M not equal to N: Iterate through the array of M elements, removing one element at a time, and building an array of the remaining M - 1 elements. Pass M-1, N, the (new) list, and the empty array. The routine calls itself. (Recurses) Iterate until the last item has been selected, then return to your caller.

Branch 2: M-x equals N but M-x and N not equal to 2 (x proportional to the depth of the call stack): Iterate through the M-x elements of the array, choosing 1 element. Put this in the first slot of the partial array. Build an array of the remaining M-x-1 elements. Pass in the parameters M-x-1, N-1, and the remaining arrays. Recurse until you have finished the iteration, then return to your caller.

Branch 3: M-x-y = N-y and N-y = 2 (y proportional to the depth of the call stack): At this point, you have two elements in the first array and N-2 elements in the second array. So put the two elements of the first array in the last two elements of the second array and output that array. Then reverse the last two elements and output that array again. Return to your caller.

I may have left out a couple of parameters, but that is the excruciating way to do it for the general case.

 

[sonny]

EMP,

If someone were to use your function "Combinations", how would they go about putting it to use on a form?

Would it be using unbound boxes such as range1, range2 (the 1- 33 as example)

How many numbers in a set in another unbound box....
How many numbers could I choose from the range in another box?

 

[ReAn]

49 choose 6 =

__49!__
6!(49-6)!

If i remember correctly from discrete math. Which is:
_______49*48*47*...*2*1________
(6*5*4*3*2*1)*(43*42*41*...*2*1)

Which is a VERY Large Number.

 

[EMP]

sonny.

The Combinations() function returns only a numeric number. To use it on a form, you can paste it to a Module. Then in the Control Source of a text box on the form, you can put something like

=Combinations(49, 6)

The text box will display the number 13,983,816


If you need to display on a form something like
3, 4, 7
3, 4, 8
3, 7, 8
4, 7, 8

as you said what you needed in your first post, you can use the form wizard to build a bound form based on Jon K's query. Jon K's sample shows how to pull the combinations from the chosen numbers. If you need more columns, you can modify his query.

The number of combinations can grow very quickly. For example, if you choose 49 numbers taken 6 at a time, the query will contain 13,983,816 records. There is very little practical use pulling a large number of combinations. I once saw someone use it to create a soccer fixture list of 40 teams playing each other i.e. Combinations(40, 2) = 780 records.



ReAn,

_______49*48*47*...*2*1________
(6*5*4*3*2*1)*(43*42*41*...*2*1)

can be shortened to


49*48*47*46*45*44
_________________ which is the formula I used in my function.
6*5*4*3*2*1

-

 

[Cosmos75]

All permutations / combinations that meet certain criteria.

 

[DLB]

Jon K,

I have been trying some VBA code to display nCr and nPr but have not been successful. I find your solution to display nC3 and nP3 by means of queries very interesting and simple.

I tried to modify your queries to display nC4 and nP4. I succeeded in the nC4 query but have not been able to make the nP4 one work correctly.

Here are the number of records displayed.

              Number of
              Records    Should have
	      Returned      been
[b] n	4	 nP4	    nP4[/b]

 4	4	  84	     24
 5	4	 260	    120
 6	4	 630	    360
 7	4	1302	    840
 8	4	2408	   1680
 9	4	4104	   3024
10	4	6570	   5040

The query displayed more records than it should be.

Can you take a look at my nP4 query and tell me how I should modify it?

Thanks in advance.

 

[Jon K]

You can think of nPr as a polygon with each field (column) being one of its sides. So nP4 is a square.

	    A
        ________
       |        |
       |        | 
     D |        | B
       |        | 
       |________|  
       
            C

In a permutation/combination, a number (i.e. an object) can appear only in one field, so the fields are related by A.Number<>B.Number, B.Number<>C.Number etc.


You have set the relationship between the adjacent sides i.e.
A.Number<>B.Number AND B.Number<>C.Number AND C.Number<>D.Number AND D.Number<>A.Number

What you need now is add the relationship between the opposite sides too:
A.Number<>C.Number AND B.Number<>D.Number


Once these two are set, the query will display the correct permutations.
See query nP4 in database.
.

 

[DLB]

Thank you!

Thank you very much Jon K.

That worked a treat. By drawing a pentagon and a 6-sided polygon, I was able to visually build the queries for nP5 and nP6.

You have provided a simple way to do it and its codeless. Thanks again.

DLB

 

[Jon K]

DLB,

When I wrote the Combinations query, I copied the condition from the Permutations query and added the < parts and it worked:-
WHERE (A.Number<>B.Number And A.Number<B.Number) And (B.Number<>C.Number And B.Number<C.Number)

Now when I re-examined the query, I saw a redundancy in the condition as it is actually the same as:-
WHERE A.Number<B.Number AND B.Number<C.Number

So you can simplify your Combinations queries by removing all the <> parts.


And to better address sonny's question, I have attached a more flexible example where the user is allowed to specify how many of the selected numbers are to be displayed in each combination, that is to specify the r in nCr, too.

A combinations query is then built and run on the fly according to the selected n and r.
.

 

[sonny]

Boy this post really blossumed. The truth be known here, a few years ago I had this idea of making a small Windows app to do what my sample db I'm now posting does. I kinda thru it together based on the responses here!

Anyways someone put the app together and it works sorta like I wanted it to. The person did'nt really understand the lotteries so his 1st draft needed some tweeking.

It had a way for the user to decide which type of game to play, IE pick3, pick4 ect... He got the pick5 and 6 correct but not the 3 & 4. No big deal... I was just gonna have him remove those two and just use the 5 & 6 features which was correct. Besides that, the only thing he was gonna fix was the print layout. He had the result in just one column and was gonna change it to 8-10 columns so it didnt take a hugh amount of paper when printing.

I use this app. It works fine as I said for the 5 & 6 games. It includes features as displayed(not all functional) in the db being posted here.
But, I now longer know his whereabouts. And I dont have the source code, just the exe. The whole app was only 1.3mb.

Anyways, now that I started to explore Access I thought perhaps it could do the same as the app did. Which, you folks kindly provided examples that it could. I'm posting the sample db only for an example of what his app kinda looked like. I did build additional queries based on the previous db posted here and a report to see if I could expand on it.

 

[Keith27]

And to better address sonny's question, I have attached a more flexible example where the user is allowed to specify how many of the selected numbers are to be displayed in each combination, that is to specify the r in nCr, too.

A combinations query is then built and run on the fly according to the selected n and r.

Jon K,

I teach Statistics in evening classes. Your sample database for building the combinations query on the fly is very useful as a demonstration tool when teaching Combinations.

Since Combinations and Permutations are related topics, I want the demonstration database to be able to build the permutations query on the fly, too. I imitated your code as much as I could but have not been able to get the condition correct for the permutations query.

Could you help me write the code for building the permutations query on the fly. I truly appreciate it and thank you in advance.

Keith

 

[Jon K]

Keith,

The attached database contains the code to build the combinations and the permutations queries on the fly with n and r in the range of 2 to 10.

Permutaions(9, 7)= 181,440
Permutaions(10, 6)= 151,200
Permutaions(10, 7)= 604,800
Permutaions(10, 10)= 3,628,800

So in permutations, a large n and r may return hundreds of thousands of records.

If you need to stop the processing of a query, you can press Ctrl+Break and click on the End button on the dialog box that pops up.
.

 

[Keith27]

A big thank you Jon K.

That's a fantastic solution!

Never thought such a complicated mathematical problem could be solved so easily using a simple query. As one poster in this thread has put it, to do it with VBA would require writing "a ton of code". I did try using VBA but I just couldn't get the loops within loops right. Operating with arrays is much more difficult than placing the numbers in a table and using a query as you do.

Thanks a lot.

Keith

 

[Jon K]

You're welcome.

Queries do have their limitations. Depending on the version of Access, when a query is too long or when the number of ANDs in it exceeds the maximum number allowed, Access will pop up an error: Query is too complex.

Luckily this occurs only if we try to pull millions or hundreds of millions of permutations. Obviously we seldom need to pull that many records.
.