# Algorithms, Code, Software to Calculate Combination Lexicographical Order, Rank, Index

## By Ion Saliu, Programmer of Lexicographic Order Software

I present here two algorithms to calculate the combination lexicographical order, or rank, or index; reversely, generate the combination for a given lexicographic order or rank. Also known as the problem of the lotto combination sequence number (CSN). The first algorithm, by B. P. Buckles and M. Lybanon; the second, by Ion Saliu. The source code is in the BASIC programming language.

First published on July 23, 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
' 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

R1 = Combine(V - C(I), K - I)  'call the combination calculator

LI = LI + R1

IF LI < L THEN
GOTO 1101
END IF

LI = LI - R1

NEXT I

C(K) = C(P1) + L – LI  ' building the array (the sought combination)

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
' 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)
REDIM Num(K)    'the numbers in the combination

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

R## = Combine(V - C(I), K - I)  'call the combination calculator

LI## = LI## + R##

IF C(I) < Num(I) THEN GOTO 2001  ' the key command by Ion Saliu

LI## = LI## - R##

NEXT I

CSN## = LI## + Num(K) - Num(P1)  'combination sequence number

---
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

REM *** This function calculates the total number of combinations ***
REM *** '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

Calculating total number of combinations is as easy as calling the Combination function. For example, a lotto 6 from 49 game:
v = 49
k = 6
TotalCombinations = Combine(v, k)

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.