The next permutation of 1342

discrete mathematicspermutations

How to find the next larger permutation 1342 in lexicographic order? I followed the algorithm in Next Permutation Algorithm based on Lexicographic ordering and I found 2134. But we know that after 1342 the next larger permutation in fact is 1423, isn't it?

Best Answer

Following the algorithm given in this answer on $1342$, and using the dreaded 1-indexing to correspond with natural language "$1$st digit, $2$nd digit" etc.:

  1. Find the largest $i$ such that the $i$th digit is less than the $(i+1)$st digit: this is $i=2$ (as $3<4$ but $4>2$).

  2. Find the largest $j>2$ such that the $j$th digit is larger than the $2$nd digit: this is $j=3$ (as $3<4$ but $3>2$).

  3. Swap the $2$nd and $3$rd digit: $1432$.

  4. Reverse the order of all digits from $2$nd onwards (not including $2$nd): $1423$.

This produces $1423$ as expected.

Related Question