Linear Search based algorithm for Mth Lexicographic ordering of Mathematical Permutation and Combina

Linear Search based algorithm for Mth Lexicographic ordering of Mathematical Permutation and Combination

 

Following the discussion in "Generating the mth Lexicographical Element of a Mathematical Combination" , I present here another algorithm for the Mth lexicographic ordering based on a linear search procedure. The method is based on the fact that it is simple to verify if Zero is the first element representing the Mth lexicographic ordering of a permutation or combination. I'll consider combinations first, followed by permutation.

Lexicographic Ordering of a Combination

Consider a combination of k elements from a set of n elements.  Let

S(k,n) represent the set of all such combinations,

C(k,n) the number of elements in the set S(k,n)

Without loss of generality we shall deal with the universe of Natural numbers including zero. Since two combinations are same if they contain the same set of elements we reduce a combination to a canonical form where it is represented as a sequence in which i-th element is greater than the (i+1)-th element. In other words let the k-tuple < s1, s2,..., sk >represent a combination. Then we can say that s1 >  s2  > ... > sk.   Also the set of all combinations are lexicographically ordered. In other words if P1 and P2 are two combinations from the same set then

P1 ≠ P2 implies (P1> P2 or P2 >P1)

Thus the M-th lexicographical element has M-1 elements in S(k,m) that are less than it and the remaining greater than it.

The Algorithm.

 Note that '0' will be the first element of the first C(k-1,n-1) elements, because having chosen '0' we are left with the problem of choosing k-1 elements from n-1 elements. If '0' is not chosen we have to choose k elements from n-1 elements yielding the well known result

C(k,n) = C(k-1,n-1) + C(k,n-1)

Thus if M<=C(k-1,n-1) then we have effectively computed the first element of the M-th sequence. If M>C(k-1,n-1) then we have reduced the problem to finding the (M-C(k-1,n-1))-th element of the ordered set S(k,n-1).

Thus the function to compute the Mth combination can be described as

1.      MthCombination(M,k,n)

2.      If (k=0)

3.      Return <>    

4.      If (k=n)

5.      return <0,1,...,k-1>

6.      if (M < C(k-1,n-1))

7.      {

8.      Let  < s1, s2,..., sk-1 > = MthCombination(M,k-1,n-1)

9.      return  < 0,s1 +1, s2 +1,...,sk-1 +1>    

10.  }

11.  B else

12.  {

13.          Let  < s1, s2,..., sk > = MthCombination(M-C(k-1,n-1),   k,  n-1)

14.  B B B B B B return <s1 +1, s2 +1,...,sk +1>

15.  B }

16.  }

The first step is to return an empty sequence if k =0.

 

Computing the Rank from a given Sequence.

Now consider the inverse problem of computing M given a combination. We shall call this the Rank of the combination.  If the first element is '0'then M<C(k-1,n-1) and hence the problem the is reduced to finding the Rank of the sequence with the first element removed. If the first element is not zero then the Rank is: C(n-1,k-1) + the rank of the combination in the set S(k-1,n) with all elements in the sequence reduced by one.  More specifically the algorithm can be described as:

Rank(< s1 ,s2 ,...,sk >, k, n)

1.      If (k=0)

2.      Return 1

3.      If s1 =0 then

4.      Return Rank(< s2-1, s3 -1, ...,s-1> , k-1, n-1)

1.      Else

2.      Return C(k-1,n-1) + Rank(< s1 -1,  s2  -1, ..., sk -1>, k,n-1)

The first step checks for an empty sequence in which case the Rank is 1.

 

Lexicographic Ordering of Permutations

 

A permutation P of N numbers can be denoted as an N-tuple (a sequence of N items)  consisting of unique elements from the set P =  {0,1,...,N-1}. In this case the sequence itself is not ordered and  every element in the set P appears once and only once in the sequence. The set of all permutations can also be linearly ordered and the M-th element defined in like manner as for the combination

The Algorithm.

Note that there are at most factorial N (denoted as N!) permuations of the set {0,1,...,N-1}; and '0' is the first element in the first (N-1)!  Permutations; '1' is the first element in the next (N-1)!  elements and so on. Hence it is simple to identify the first element. Let the first element be 'j'. The problem is now reduced to finding the  (M - (N-1)! * j)-th element of the set of permutations of (N-1) numbers.  Combining the two results consists of appropriately changing the second sequence so that the number j is not repeated. This is easily done by incrementing all si >= j by 1, where si is the i-th element of the resulting sequence.

1.       PermutationM( M, N)

1.      B {

2.      B B if (N=0)

3.      B B B B return <>

4.      else

5.      {

6.      B B B B m =( N-1)!

7.      B B B B m0 = m

8.      B B B while (M > m)

9.      B B {

10.  B B B B m = m+m0

11.  B B }

12.  B B Let  < s1, s2,..., sN-1 > = PermutationM (M- (m-m0), n-1)

13.  B B Return <k, Ik(s1 ), Ik(s2),..., Ik(sN-1 )>

14.  }

 Here

 Ik (i) = i if (i<k)

        = i+1 if (i=>k)

 

 

Rank of a Permutation

       

Consider the inverse problem of computing M the rank of a given permutation of N numbers.  The first element determines into which block of (N-1)!  elements, the given permutation falls. The problem then can be reduced to finding the rank of suffix of the permutation until we have an empty sequence in which case the rank is 1. The algorithm is outlined in more detail as follows:

1.       Rank(<s1, s2,..., sN>,N )

1.        if (0 == n)

2.      return 1

3.      else

4.      k=s1

5.      return (k-1) *(N-1)! + Rank(<Dk(s1 ), Dk(s2),..., Dk(sN-1 )>,N-1);

where

Dk(i) B B = i if i<k

= i-1 if i>=k



About the Author

Joe Mariadassou

Joe is programmer focussing on the Windows/C++ space. He loves developing algorithms and formal programming such as contracts and proving program correctness.

Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: May 11, 2015 @ 1:00 p.m. ET / 10:00 a.m. PT One of the languages that have always been supported with the Intel® RealSense™ SDK (Software Developer Kit) is JavaScript, specifically so that web-enabled apps could be created. Come hear from Intel Expert Bob Duffy as he reviews his own little "space shooting" game where the orientation of your face controls the aiming reticle to help teach developers how to write apps and games in JavaScript that can use facial and gesture …

  • Live Event Date: May 6, 2015 @ 1:00 p.m. ET / 10:00 a.m. PT Where are you in your plans to adopt Disaster Recovery-as-a-Service? Are you just getting started? Fighting an uphill battle with management? At Cisco, Zerto and iland, we've seen it all – from the early adopters who excitedly rushed to implement DRaaS with us nine years ago to the IT folks dragging their business leaders into the future. With our years of experience, we've learned there are six types of DRaaS leaders – but which type …

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date