Science Software: Statistics, Probability, Odds, Combinatorial Mathematics, Algorithms.

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

Software Source Code in BASIC: The First Two Algorithms

By Ion Saliu, Programmer of Lexicographic Order Software

First complete algorithms of calculating lexicographical order, CSN, combination sequence number.

• First published on July 23, 2001.
•• First captured by the WayBack Machine (web.archive.org) on August 10, 2001.

Two algorithms in software to calculate the combination lexicographical order, or rank, or index.

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

  ' 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

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

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)

Pay Membership, Download Software: Lottery, Gambling, Roulette, Sports, Powerball, Mega Millions.

Right-click to download:

Ion Saliu's Theory of Probability Book founded on valuable mathematics, including lexicographic ordering. 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.

Algorithm, algorithms, formula, formulas, formulae for index, lexicographic, 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.

You study algorithms of combinatorial mathematics of lexicographic, lexicographical order.

Home | Search | New Writings | Software | Odds, Generator | Contents | Forums | Sitemap

This is combinatorics at its best: Algorithms, source code to calculate lexicographic order.