• First published on July 23, 2001.
•• First captured by the WayBack Machine (web.archive.org) on August 10, 2001.
When you gotta do it, you'll do it. For your mind won't find peace until a goal is reached. I presented earlier this month of July 2001 an algorithm to calculate the index, or rank, or lexicographical order, or combination sequence number (CSN). The algorithm was 100% precise. It had one problem, however. The speed of execution left much to be desired for monster-odds games, such as Keno (80/20, 70/20, even 70/10). The speed was acceptable for many other lotto games. Even a big game such as the 49/5/42 PowerBall required less than half a minute to determine the CSN. Nevertheless, running the algorithm for Keno games took an eternity!
I came back to the original B. P. Buckles and M. Lybanon algorithm (algorithm ACM #515). I was able to add to it the reverse task: Calculate the CSN for any lotto game, but the Powerball. Later, the PowerBall was added to the procedure, plus a function for Euromillions.
I recompiled NTHINDEX to SEQUENCE, the program that uses the new algorithm. All my lexicographical order software is freeware at the software download site (but only for registered members).
There you have the two main algorithms for the combinatorics tasks of lexicographic ordering. Listed is also my function that calculates the number of combinations N taken M at a time: Combine## (N, M).
Here is the very first lexicographic order algorithm for the sets known as combinations (e.g. lotto drawings). The lexicographic order algorithm was developed by B. P. Buckles and M. Lybanon to determine the combination for a given rank (index or lexicographic order). The algorithm is included in the Association for Computing Machinery (ACM algorithm #515, published in 1977).
' *** the first combination lexicographic order algorithm by B. P. Buckles and M. Lybanon
In 2001 I discovered the opposite algorithm: Calculate the index (lexicographical order) when the combination is given.
' *** the new 'combination index (rank)' algorithm by Ion Saliu
Calculating total number of combinations is as easy as calling the Combination function. For example, a lotto 6 from 49 game:
~ FindCombo, the function that finds the combination for a given index (the original algorithm by B. P. Buckles and M. Lybanon);
' converted from FORTRAN to BASIC
' V = the biggest number in the lotto game (e.g. 49, or 80, etc.)
' K = numbers per combination (e.g. 6, 10, 20, etc.)
' L = lexicographical index to find a combination (e.g. the 1st, the last, 100005th, etc.)
REDIM C(K)
LI## = 0
P1 = K - 1
FOR I = 1 TO P1
C(I) = 0
IF I < > 1 THEN
C(I) = C(I - 1)
END IF
1101 C(I) = C(I) + 1
' call the combination calculator
R1 = Combine(V - C(I), K - I)
LI = LI + R1
IF LI < L THEN
GOTO 1101
END IF
LI = LI - R1
NEXT I
' building the array (the sought combination)
C(K) = C(P1) + L – LI
' V = the biggest number in the lotto game (e.g. 49, or 80, etc.)
' K = numbers per combination (e.g. 6, 10, 20, etc.)
REDIM C(K)
' the numbers in the combination
REDIM Num(K)
LI## = 0
CSN## = 0
P1 = K - 1
FOR I = 1 TO P1
C(I) = 0
If I < > 1 THEN C(I) = C(I - 1)
2001 C(I) = C(I) + 1
' call the combination calculator
R## = Combine(V - C(I), K - I)
LI## = LI## + R##
' the key command by Ion Saliu
IF C(I) < Num(I) THEN GOTO 2001
LI## = LI## - R##
NEXT I
'combination sequence number CSN
CSN## = LI## + Num(K) - Num(P1)
---
FUNCTION Combine(N AS LONG, M AS LONG) AS EXT
DIM iC AS LONG
DIM jC AS LONG
DIM FA AS EXT
DIM va AS EXT
' This function calculates the total number of
' combinations N taken M at a time
FA = 1
FOR iC = 1 TO M
FA = FA * iC
NEXT iC
va = 1
FOR jC = (N - M + 1) TO N
va = va * jC
NEXT jC
Combine = va / FA
END FUNCTION
v = 49
k = 6
TotalCombinations = Combine(v, k)
~ FindIndex, the function that finds the index for a given combination (Ion Saliu's lexicographic algorithm).
Right-click to download:
Read Ion Saliu's first book in print: Probability Theory, Live!
~ Founded on valuable mathematical discoveries with a wide range of scientific applications, including the organic connection between probability theory and sets of numbers — permutations, combinations, arrangements, lexicographical order.
This is a comprehensive list of my writings on the topic of lexicographical order or indexing, including algorithms and software.
Of course, everybody loves to feast on great software, especially when it is free! My combinatorics software (and other categories) is absolutely free to run, for an unlimited period of time. However, only the registered members have a right to download the software. Membership requires a nominal fee — the most reasonable there is to connect to the greatest and most useful software ever created. No kidding! Read the conditions to becoming a registered member: Download Great Free Software: Paid Membership Required.