3
$\begingroup$

I have a group of contiguous digits ordered from smallest to highest: 1234. I want a formula (in case it exists) to find the next closer higher permutation of the same digits. In this example the next few permutations would be:

(1234) 1243 1324 1342 1423 1432, and so on...

I noticed that the next permutation is always at a distance that is a multiple (I) of 9, but follows a pattern that I don't get. That way, each successive permutation always equals 9I + previous permutation. Combinating manually I obtained the value I of 23 successive permutations (4!-original permutation), here are a few:

Permutation: I Value

  • 1st: N/A (Original permutation)
  • 2nd: 1
  • 3rd: 9
  • 4th: 2
  • 5th: 9
  • 6th: 1
  • 7th: 78
  • ...

So, is there a formula to predict the next permutation? Thanks a lot for your help!!

$\endgroup$

1 Answer 1

3
$\begingroup$

I believe you mean permutations, rather than combinations. I am unaware of any single formula, per se. However, there is an algorithm, that you could use. It makes use of the factoradiac number system (also known as the factorial number system) and the Lehmer code. https://en.wikipedia.org/wiki/Factorial_number_system & https://en.wikipedia.org/wiki/Lehmer_code

The process of finding ascending permutations of the given $n$ digits is:

  1. Write down $0$ to $n!-1$ in factorial number system.
  2. These numbers are Lehmer codes for the permutation. Convert these codes to corresponding permutations. The resulting series is what you are looking for.

Let us consider a case where the number of elements is $4$, as you showed in your problem. The $4$ elements in ascending order are: $a,b,c,d$. Their permutations will result in $4\times 3\times 2 \times 1 = 4! = 24$ outcomes. Let us call the set of all the outcomes as the permutation set, and each permutation outcome as the permutation number. Each permutation number consists of 4 digits, chosen from the ${a,b,c,d}$. Each permutation number in this set is mapped to a number between $0$ to $23$. The smallest number $abcd$ is mapped to $0$, the next higher number $abdc$ is mapped to $1$, and so on.. until, the highest number $dcba$, which is mapped to $23$.

Step 1: Convert the numbers $0$ to $23$ to the factorial number system. The process involves writing the number as a linear sum of factorials. For example, in base 10, we know that $23 = 2\times10^1+3\times 10^0$. In the factorial base, it is: \begin{align} 23 &= 3 \times 3! + 2 \times 2! + 1 \times 1! + 0\times 0!\\ &=3210_{!} \end{align} Another example, $119$: \begin{align} 119 &= 4\times 4!+3 \times 3! + 2 \times 2! + 1 \times 1! + 0\times 0!\\ &=43210_{!} \end{align}

An interesting characteristic to note is that that in the factorial number system, you need $n$-digits to write down a number that's smaller than $n!$. So, $23$, which is smaller than $4! = 24$, would require $4$ digits. And $119$, which is smaller than $5! = 120$ requires 5 digits. The last digit of all factorial numbers is always kept 0.

For your ease of understanding, some numbers in factorial system are: \begin{align} 0 &=0000\\ 1 &=0010\\ 2 &=0100\\ 3 &=0110\\ \vdots &= \vdots \\ 21 & = 3110 \\ 22 & = 3200 \\ 23 & = 3210 \end{align} Another interesting property is that The digits used to make these factorial based numbers are from $0$ to $3$ (i.e., from $0$ to $n-1$).

Step 2: Now comes the tricky part. The conversion between the factorial number system to the permutation number is carried our by the Lehmer code. Each digit in the factorial number system gives us information about the corresponding digit from the permutation number. So, the the first digit in factorial number tells us about the first digit in the permutation number and so on. If a factorial number digit reads $x$, then the permutation number digit in that spot is the $(x+1)^{th}$ smallest element of the $remaining$ choices. Allow me to illustrate:

Take $23 = 3210_{!}$ as an example. The corresponding elements at each digit are

\begin{array}{ccc} \text{digit} & \text{elements remaining} & \text{element chosen} \\ 3 & abcd & d\\ 2 & abc & c\\ 1 & ab & b\\ 0 & a & a \end{array} The permutation number is $dcba$

Similarly, take $13 = 2010_{!}$ \begin{array}{ccc} \text{digit} & \text{elements remaining} & \text{element chosen} \\ 2 & abcd & c\\ 0 & abd & a\\ 1 & bd & d\\ 0 & a & b \end{array} The permutation is $cadb$

So, you know $0 = 0000_{!} = abcd$. The next element, $1 = 0010_{!}$ is: \begin{array}{ccc} \text{digit} & \text{elements remaining} & \text{element chosen} \\ 0 & abcd & a\\ 0 & bcd & b\\ 1 & cd & d\\ 0 & c & c \end{array} As expected, the permutation number is $abdc$ which is the next higher number from $abcd$. Carry this out for $2,3,\dots,23$

Now, suppose you know an n-digit permutation number ($p$) and you want to find its next higher permutation number ($q$). Convert $p$ to Lehmer code in a manner reverse of the above. This will be a n-digit number ($w$) in the factorial number system. Convert it to decimal system, add 1, and convert it back to factorial number system. Then using Lehmer code, find the permutation number ($q$).

Permutation number $adcb = 0210$ in Lehmer code. This factorial system number $0210_{!}$ is infact, $5$ in the decimal system. Adding $1$, we get $6$ which is $1000_{!}$. Using that as Lehmer code, we find the next permutation number as $bacd$.

$\endgroup$
1
  • $\begingroup$ Thank you for your detailed explanation. $\endgroup$
    – Michael C.
    Jun 21, 2022 at 21:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .