Fast permutation -> number -> permutation mapping

Question

I have n elements. For the sake of an example, let's say, 7 elements, 1234567. I know there are 7! = 5040 permutations possible of these 7 elements.

I want a fast algorithm comprising two functions:

f(number) maps a number between 0 and 5039 to a unique permutation, and

f'(permutation) maps the permutation back to the number that it was generated from.

I don't care about the correspondence between number and permutation, providing each permutation has its own unique number.

So, for instance, I might have functions where

f(0) = '1234567'
f'('1234567') = 0

The fastest algorithm that comes to mind is to enumerate all permutations and create a lookup table in both directions, so that, once the tables are created, f(0) would be O(1) and f('1234567') would be a lookup on a string. However, this is memory hungry, particularly when n becomes large.

Can anyone propose another algorithm that would work quickly and without the memory disadvantage?

Answer 1

The complexity can be brought down to n*log(n), see section 10.1.1 ("The Lehmer code (inversion table)", p.232ff) of the fxtbook: http://www.jjj.de/fxt/#fxtbook skip to section 10.1.1.1 ("Computation with large arrays" p.235) for the fast method. The (GPLed, C++) code is on the same web page.

Answer 2

I was hasty in my previous answer (deleted), I do have the actual answer though. It is provided by a similar concept, the factoradic, and is related to permutations (my answer related to combinations, I apologize for that confusion). I hate to just post wikipedia links, but I writeup I did awhile ago is unintelligible for some reason. So, I can expand on this later if requested.

Answer 3

Problem solved. However, I am not sure you still need the solution after these years. LOL, I just join this site, so ... Check my Java Permutation Class. You can base on an index to get a symbol permutation, or give a symbol permutation then get the index.

Here is my Premutation Class

/**
 ****************************************************************************************************************
 * Copyright 2015 Fred Pang [e-mail]
 ****************************************************************************************************************
 * A complete list of Permutation base on an index.
 * Algorithm is invented and implemented by Fred Pang [e-mail]
 * Created by Fred Pang on 18/11/2015.
 ****************************************************************************************************************
 * LOL this is my first Java project. Therefore, my code is very much like C/C++. The coding itself is not
 * very professional. but...
 *
 * This Permutation Class can be use to generate a complete list of all different permutation of a set of symbols.
 * nPr will be n!/(n-r)!
 * the user can input       n = the number of items,
 *                          r = the number of slots for the items,
 *                          provided n >= r
 *                          and a string of single character symbols
 *
 * the program will generate all possible permutation for the condition.
 *
 * Say if n = 5, r = 3, and the string is "12345", it will generate sll 60 different permutation of the set
 * of 3 character strings.
 *
 * The algorithm I used is base on a bin slot.
 * Just like a human or simply myself to generate a permutation.
 *
 * if there are 5 symbols to chose from, I'll have 5 bin slot to indicate which symbol is taken.
 *
 * Note that, once the Permutation object is initialized, or after the constructor is called, the permutation
 * table and all entries are defined, including an index.
 *
 * eg. if pass in value is 5 chose 3, and say the symbol string is "12345"
 * then all permutation table is logically defined (not physically to save memory).
 * It will be a table as follows
 *  index  output
 *      0   123
 *      1   124
 *      2   125
 *      3   132
 *      4   134
 *      5   135
 *      6   143
 *      7   145
 *      :     :
 *      58  542
 *      59  543
 *
 * all you need to do is call the "String PermGetString(int iIndex)" or the "int[] PermGetIntArray(int iIndex)"
 * function or method with an increasing iIndex, starting from 0 to getiMaxIndex() - 1. It will return the string
 * or the integer array corresponding to the index.
 *
 * Also notice that in the input string is "12345" of  position 01234, and the output is always in accenting order
 * this is how the permutation is generated.
 *
 * ***************************************************************************************************************
 * ====  W a r n i n g  ====
 * ***************************************************************************************************************
 *
 * There is very limited error checking in this class
 *
 * Especially the  int PermGetIndex(int[] iInputArray)  method
 * if the input integer array contains invalid index, it WILL crash the system
 *
 * the other is the string of symbol pass in when the object is created, not sure what will happen if the
 * string is invalid.
 * ***************************************************************************************************************
 *
 */
public class Permutation
{
    private boolean bGoodToGo = false;      // object status
    private boolean bNoSymbol = true;
    private BinSlot slot;                   // a bin slot of size n (input)
    private int nTotal;                     // n number for permutation
    private int rChose;                     // r position to chose
    private String sSymbol;                 // character string for symbol of each choice
    private String sOutStr;
    private int iMaxIndex;                  // maximum index allowed in the Get index function
    private int[] iOutPosition;             // output array
    private int[] iDivisorArray;            // array to do calculation

    public Permutation(int inCount, int irCount, String symbol)
    {
        if (inCount >= irCount)
        {
            // save all input values passed in
            this.nTotal = inCount;
            this.rChose = irCount;
            this.sSymbol = symbol;

            // some error checking
            if (inCount < irCount || irCount <= 0)
                return;                                 // do nothing will not set the bGoodToGo flag

            if (this.sSymbol.length() >= inCount)
            {
                bNoSymbol = false;
            }

            // allocate output storage
            this.iOutPosition = new int[this.rChose];

            // initialize the bin slot with the right size
            this.slot = new BinSlot(this.nTotal);

            // allocate and initialize divid array
            this.iDivisorArray = new int[this.rChose];

            // calculate default values base on n & r
            this.iMaxIndex = CalPremFormula(this.nTotal, this.rChose);

            int i;
            int j = this.nTotal - 1;
            int k = this.rChose - 1;

            for (i = 0; i < this.rChose; i++)
            {
                this.iDivisorArray[i] = CalPremFormula(j--, k--);
            }
            bGoodToGo = true;       // we are ready to go
        }
    }

    public String PermGetString(int iIndex)
    {
        if (!this.bGoodToGo) return "Error: Object not initialized Correctly";
        if (this.bNoSymbol) return "Error: Invalid symbol string";
        if (!this.PermEvaluate(iIndex)) return "Invalid Index";

        sOutStr = "";
        // convert string back to String output
        for (int i = 0; i < this.rChose; i++)
        {
            String sTempStr = this.sSymbol.substring(this.iOutPosition[i], iOutPosition[i] + 1);
            this.sOutStr = this.sOutStr.concat(sTempStr);
        }
        return this.sOutStr;
    }

    public int[] PermGetIntArray(int iIndex)
    {
        if (!this.bGoodToGo) return null;
        if (!this.PermEvaluate(iIndex)) return null ;
        return this.iOutPosition;
    }

    // given an int array, and get the index back.
    //
    //  ====== W A R N I N G ======
    //
    // there is no error check in the array that pass in
    // if any invalid value in the input array, it can cause system crash or other unexpected result
    //
    // function pass in an int array generated by the PermGetIntArray() method
    // then return the index value.
    //
    // this is the reverse of the PermGetIntArray()
    //
    public int PermGetIndex(int[] iInputArray)
    {
        if (!this.bGoodToGo) return -1;
        return PermDoReverse(iInputArray);
    }


    public int getiMaxIndex() {
    return iMaxIndex;
}

    // function to evaluate nPr = n!/(n-r)!
    public int CalPremFormula(int n, int r)
    {
        int j = n;
        int k = 1;
        for (int i = 0; i < r; i++, j--)
        {
            k *= j;
        }
        return k;
    }


//  PermEvaluate function (method) base on an index input, evaluate the correspond permuted symbol location
//  then output it to the iOutPosition array.
//
//  In the iOutPosition[], each array element corresponding to the symbol location in the input string symbol.
//  from location 0 to length of string - 1.

    private boolean PermEvaluate(int iIndex)
    {
        int iCurrentIndex;
        int iCurrentRemainder;
        int iCurrentValue = iIndex;
        int iCurrentOutSlot;
        int iLoopCount;

        if (iIndex >= iMaxIndex)
            return false;

        this.slot.binReset();               // clear bin content
        iLoopCount = 0;
        do {
            // evaluate the table position
            iCurrentIndex = iCurrentValue / this.iDivisorArray[iLoopCount];
            iCurrentRemainder = iCurrentValue % this.iDivisorArray[iLoopCount];

            iCurrentOutSlot = this.slot.FindFreeBin(iCurrentIndex);     // find an available slot
            if (iCurrentOutSlot >= 0)
                this.iOutPosition[iLoopCount] = iCurrentOutSlot;
            else return false;                                          // fail to find a slot, quit now

            this.slot.setStatus(iCurrentOutSlot);                       // set the slot to be taken
            iCurrentValue = iCurrentRemainder;                          // set new value for current value.
            iLoopCount++;                                               // increase counter
        } while (iLoopCount < this.rChose);

        // the output is ready in iOutPosition[]
        return true;
    }

    //
    // this function is doing the reverse of the permutation
    // the input is a permutation and will find the correspond index value for that entry
    // which is doing the opposit of the PermEvaluate() method
    //
    private int PermDoReverse(int[] iInputArray)
    {
        int iReturnValue = 0;
        int iLoopIndex;
        int iCurrentValue;
        int iBinLocation;

        this.slot.binReset();               // clear bin content

        for (iLoopIndex = 0; iLoopIndex < this.rChose; iLoopIndex++)
        {
            iCurrentValue = iInputArray[iLoopIndex];
            iBinLocation = this.slot.BinCountFree(iCurrentValue);
            this.slot.setStatus(iCurrentValue);                          // set the slot to be taken
            iReturnValue = iReturnValue + iBinLocation * this.iDivisorArray[iLoopIndex];
        }
        return iReturnValue;
    }


    /*******************************************************************************************************************
     *******************************************************************************************************************
     * Created by Fred on 18/11/2015.   [e-mail]
     *
     * *****************************************************************************************************************
     */
    private static class BinSlot
    {
        private int iBinSize;       // size of array
        private short[] eStatus;    // the status array must have length iBinSize

        private BinSlot(int iBinSize)
        {
            this.iBinSize = iBinSize;               // save bin size
            this.eStatus = new short[iBinSize];     // llocate status array
        }

        // reset the bin content. no symbol is in use
        private void binReset()
        {
            // reset the bin's content
            for (int i = 0; i < this.iBinSize; i++) this.eStatus[i] = 0;
        }

        // set the bin position as taken or the number is already used, cannot be use again.
        private void  setStatus(int iIndex) { this.eStatus[iIndex]= 1; }

        //
        // to search for the iIndex th unused symbol
        // this is important to search through the iindex th symbol
        // because this is how the table is setup. (or the remainder means)
        // note: iIndex is the remainder of the calculation
        //
        // for example:
        // in a 5 choose 3 permutation symbols "12345",
        // the index 7 item (count starting from 0) element is "1 4 3"
        // then comes the index 8, 8/12 result 0 -> 0th symbol in symbol string = '1'
        // remainder 8. then 8/3 = 2, now we need to scan the Bin and skip 2 unused bins
        //              current the bin looks 0 1 2 3 4
        //                                    x o o o o     x -> in use; o -> free only 0 is being used
        //                                      s s ^       skipped 2 bins (bin 1 and 2), we get to bin 3
        //                                                  and bin 3 is the bin needed. Thus symbol "4" is pick
        // in 8/3, there is a remainder 2 comes in this function as 2/1 = 2, now we have to pick the empty slot
        // for the new 2.
        // the bin now looks 0 1 2 3 4
        //                   x 0 0 x 0      as bin 3 was used by the last value
        //                     s s   ^      we skip 2 free bins and the next free bin is bin 4
        //                                  therefor the symbol "5" at the symbol array is pick.
        //
        // Thus, for index 8  "1 4 5" is the symbols.
        //
        //
        private int FindFreeBin(int iIndex)
        {
            int j = iIndex;

            if (j < 0 || j > this.iBinSize) return -1;               // invalid index

            for (int i = 0; i < this.iBinSize; i++)
            {
                if (this.eStatus[i] == 0)       // is it used
                {
                    // found an empty slot
                    if (j == 0)                 // this is a free one we want?
                        return i;               // yes, found and return it.
                    else                        // we have to skip this one
                        j--;                    // else, keep looking and count the skipped one
                }
            }
            assert(true);           // something is wrong
            return -1;              // fail to find the bin we wanted
        }

        //
        // this function is to help the PermDoReverse() to find out what is the corresponding
        // value during should be added to the index value.
        //
        // it is doing the opposite of int FindFreeBin(int iIndex) method. You need to know how this
        // FindFreeBin() works before looking into this function.
        //
        private int BinCountFree(int iIndex)
        {
            int iRetVal = 0;
            for (int i = iIndex; i > 0; i--)
            {
                if (this.eStatus[i-1] == 0)       // it is free
                {
                    iRetVal++;
                }
            }
            return iRetVal;
        }
    }
}
// End of file - Permutation.java

and here is my Main Class for showing how to use the class.

/*
 * copyright 2015 Fred Pang
 *
 * This is the main test program for testing the Permutation Class I created.
 * It can be use to demonstrate how to use the Permutation Class and its methods to generate a complete
 * list of a permutation. It also support function to get back the index value as pass in a permutation.
 *
 * As you can see my Java is not very good. :)
 * This is my 1st Java project I created. As I am a C/C++ programmer for years.
 *
 * I still have problem with the Scanner class and the System class.
 * Note that there is only very limited error checking
 *
 *
 */

import java.util.Scanner;

public class Main
{
    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args)
    {
        Permutation perm;       // declear the object
        String sOutString = "";
        int nCount;
        int rCount;
        int iMaxIndex;

        // Get user input
        System.out.println("Enter n: ");
        nCount = scanner.nextInt();

        System.out.println("Enter r: ");
        rCount = scanner.nextInt();

        System.out.println("Enter Symbol: ");
        sOutString = scanner.next();

        if (sOutString.length() < rCount)
        {
            System.out.println("String too short, default to numbers");
            sOutString = "";
        }

        // create object with user requirement
        perm = new Permutation(nCount, rCount, sOutString);

        // and print the maximum count
        iMaxIndex = perm.getiMaxIndex();
        System.out.println("Max count is:" + iMaxIndex);

        if (!sOutString.isEmpty())
        {
            for (int i = 0; i < iMaxIndex; i++)
            {   // print out the return permutation symbol string
                System.out.println(i + " " + perm.PermGetString(i));
            }
        }
        else
        {
            for (int i = 0; i < iMaxIndex; i++)
            {
                System.out.print(i + " ->");

                // Get the permutation array
                int[] iTemp = perm.PermGetIntArray(i);

                // print out the permutation
                for (int j = 0; j < rCount; j++)
                {
                    System.out.print(' ');
                    System.out.print(iTemp[j]);
                }

                // to verify my PermGetIndex() works. :)
                if (perm.PermGetIndex(iTemp)== i)
                {
                    System.out.println(" .");
                }
                else
                {   // oops something is wrong :(
                    System.out.println(" ***************** F A I L E D *************************");
                    assert(true);
                    break;
                }
            }
        }
    }
}
//
// End of file - Main.java

Have fun. :)

Answer 4

A related question is computing the inverse permutation, a permutation which will restore permuted vectors to original order when only the permutation array is known. Here is the O(n) code (in PHP):

// Compute the inverse of a permutation
function GetInvPerm($Perm)
    {
    $n=count($Perm);
    $InvPerm=[];
    for ($i=0; $i<$n; ++$i)
        $InvPerm[$Perm[$i]]=$i;
    return $InvPerm;
    } // GetInvPerm

David Spector Springtime Software

Answer 5

I made an algorithm in O(n), you can get my functions here: http://antoinecomeau.blogspot.ca/2014/07/mapping-between-permutations-and.html

public static int[] perm(int n, int k)
{
    int i, ind, m=k;
    int[] permuted = new int[n];
    int[] elems = new int[n];

    for(i=0;i<n;i++) elems[i]=i;

    for(i=0;i<n;i++)
    {
            ind=m%(n-i);
            m=m/(n-i);
            permuted[i]=elems[ind];
            elems[ind]=elems[n-i-1];
    }

    return permuted;
}

public static int inv(int[] perm)
{
    int i, k=0, m=1;
    int n=perm.length;
    int[] pos = new int[n];
    int[] elems = new int[n];

    for(i=0;i<n;i++) {pos[i]=i; elems[i]=i;}

    for(i=0;i<n-1;i++)
    {
            k+=m*pos[perm[i]];
            m=m*(n-i);
            pos[elems[n-i-1]]=pos[perm[i]];
            elems[pos[perm[i]]]=elems[n-i-1];
    }

    return k;
}

Answer 6

To describe a permutation of n elements, you see that for the position that the first element ends up at, you have n possibilities, so you can describe this with a number between 0 and n-1. For the position that the next element ends up at, you have n-1 remaining possibilities, so you can describe this with a number between 0 and n-2.
Et cetera until you have n numbers.

As an example for n = 5, consider the permutation that brings abcde to caebd.

• a, the first element, ends up at the second position, so we assign it index 1.
• b ends up at the fourth position, which would be index 3, but it's the third remaining one, so we assign it 2.
• c ends up at the first remaining position, which is always 0.
• d ends up at the last remaining position, which (out of only two remaining positions) is 1.
• e ends up at the only remaining position, indexed at 0.

So we have the index sequence {1, 2, 0, 1, 0}.

Now you know that for instance in a binary number, 'xyz' means z + 2y + 4x. For a decimal number,
it's z + 10y + 100x. Each digit is multiplied by some weight, and the results are summed. The obvious pattern in the weight is of course that the weight is w = b^k, with b the base of the number and k the index of the digit. (I will always count digits from the right and starting at index 0 for the rightmost digit. Likewise when I talk about the 'first' digit I mean the rightmost.)

The reason why the weights for digits follow this pattern is that the highest number that can be represented by the digits from 0 to k must be exactly 1 lower than the lowest number that can be represented by only using digit k+1. In binary, 0111 must be one lower than 1000. In decimal, 099999 must be one lower than 100000.

Encoding to variable-base
The spacing between subsequent numbers being exactly 1 is the important rule. Realising this, we can represent our index sequence by a variable-base number. The base for each digit is the amount of different possibilities for that digit. For decimal each digit has 10 possibilities, for our system the rightmost digit would have 1 possibility and the leftmost will have n possibilities. But since the rightmost digit (the last number in our sequence) is always 0, we leave it out. That means we're left with bases 2 to n. In general, the k'th digit will have base b[k] = k + 2. The highest value allowed for digit k is h[k] = b[k] - 1 = k + 1.

Our rule about the weights w[k] of digits requires that the sum of h[i] * w[i], where i goes from i = 0 to i = k, is equal to 1 * w[k+1]. Stated recurrently, w[k+1] = w[k] + h[k] * w[k] = w[k]*(h[k] + 1). The first weight w[0] should always be 1. Starting from there, we have the following values:

k    h[k] w[k]    

0    1    1  
1    2    2    
2    3    6    
3    4    24   
...  ...  ...
n-1  n    n!  

(The general relation w[k-1] = k! is easily proved by induction.)

The number we get from converting our sequence will then be the sum of s[k] * w[k], with k running from 0 to n-1. Here s[k] is the k'th (rightmost, starting at 0) element of the sequence. As an example, take our {1, 2, 0, 1, 0}, with the rightmost element stripped off as mentioned before: {1, 2, 0, 1}. Our sum is 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37.

Note that if we take the maximum position for every index, we'd have {4, 3, 2, 1, 0}, and that converts to 119. Since the weights in our number encoding were chosen so that we don't skip any numbers, all numbers 0 to 119 are valid. There are precisely 120 of these, which is n! for n = 5 in our example, precisely the number of different permutations. So you can see our encoded numbers completely specify all possible permutations.

Decoding from variable-base
Decoding is similar to converting to binary or decimal. The common algorithm is this:

int number = 42;
int base = 2;
int[] bits = new int[n];

for (int k = 0; k < bits.Length; k++)
{
    bits[k] = number % base;
    number = number / base;
}

For our variable-base number:

int n = 5;
int number = 37;

int[] sequence = new int[n - 1];
int base = 2;

for (int k = 0; k < sequence.Length; k++)
{
    sequence[k] = number % base;
    number = number / base;

    base++; // b[k+1] = b[k] + 1
}

This correctly decodes our 37 back to {1, 2, 0, 1} (sequence would be {1, 0, 2, 1} in this code example, but whatever ... as long as you index appropriately). We just need to add 0 at the right end (remember the last element always has only one possibility for its new position) to get back our original sequence {1, 2, 0, 1, 0}.

Permuting a list using an index sequence
You can use the below algorithm to permute a list according to a specific index sequence. It's an O(n²) algorithm, unfortunately.

int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];

for (int i = 0; i < n; i++)
{
    int s = sequence[i];
    int remainingPosition = 0;
    int index;

    // Find the s'th position in the permuted list that has not been set yet.
    for (index = 0; index < n; index++)
    {
        if (!set[index])
        {
            if (remainingPosition == s)
                break;

            remainingPosition++;
        }
    }

    permuted[index] = list[i];
    set[index] = true;
}

Common representation of permutations
Normally you would not represent a permutation as unintuitively as we've done, but simply by the absolute position of each element after the permutation is applied. Our example {1, 2, 0, 1, 0} for abcde to caebd is normally represented by {1, 3, 0, 4, 2}. Each index from 0 to 4 (or in general, 0 to n-1) occurs exactly once in this representation.

Applying a permutation in this form is easy:

int[] permutation = new int[] { 1, 3, 0, 4, 2 };

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

for (int i = 0; i < n; i++)
{
    permuted[permutation[i]] = list[i];
}

Inverting it is very similar:

for (int i = 0; i < n; i++)
{
    list[i] = permuted[permutation[i]];
}

Converting from our representation to the common representation
Note that if we take our algorithm to permute a list using our index sequence, and apply it to the identity permutation {0, 1, 2, ..., n-1}, we get the inverse permutation, represented in the common form. ({2, 0, 4, 1, 3} in our example).

To get the non-inverted premutation, we apply the permutation algorithm I just showed:

int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];

for (int i = 0; i < n; i++)
{
    normal[identity[i]] = list[i];
}

Or you can just apply the permutation directly, by using the inverse permutation algorithm:

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

int[] inverted = { 2, 0, 4, 1, 3 };

for (int i = 0; i < n; i++)
{
    permuted[i] = list[inverted[i]];
}

Note that all the algorithms for dealing with permutations in the common form are O(n), while applying a permutation in our form is O(n²). If you need to apply a permutation several times, first convert it to the common representation.