Algorithm, algorithms, formula calculate combination lexicographic order, lexicographical order.

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

Learn here mathematics, formula, formulas, formulae of lexicographic, lexicographical order.

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.EXE to SEQUENCE.EXE, 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)

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.

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

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

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