2019-09-16

Recently, while surfing threw YouTube I saw a video where someone mentioned his “favorite algorithm”. Whenever I hear the word “algorithm” there is only one in my mind. We have a history. This algorithm is almost a friend.

Back in 2007 (during my diploma studies), we had to implement a software which had a part of searching the “best” operation respecting amongst others input- and return-parameters. Therefor we had to search for all combinations of the parameters. But the number of permutations is factorial so you can very quickly have a massive number of possible permutations.

We decided to implement an algorithm to get the next permutation, only when we needed it. So we had no list of all possible permutations in memory but just the current one. But it wasn’t easy to find an algorithm. We searched a lot (I turns out maybe not really efficient) but didn’t find one in the first place. So I spent hours and hours to get a solution myself. Lots of slips of paper where lying everywhere and my young ambition was aroused. I had to find a solution for this problem. This was really so much fun. I really loved, and still do, to sink my teeth into such kind of technical problems.

I can’t remember, if I found the solution myself (maybe not – if so I would remember), but we finally found an algorithm inside the book “Discrete Mathematics and Its Applications” which described how to generate the next permutation in lexicographic order. Again it was a challenge to implement it in a way that everyone could easy understand it. Our documentation had an appendix with an example and a pseudo code implementation because it seems to be not easy to understand after describing it as text.

After more than 10 years I still remember how much fun I had and how challenging it was for me to solve the problem. That’s the reason why I would call this algorithm my favorite one. But I never found a name for it, as the book refers it as “Generating the Next Permutation in Lexicographic Order”.

I’m happy to share it anyway. Just for completeness. And to practice again how to put it in words. 😉

// For this code snippet I choose an implementation taking the current
// permutation as an input parameter.
public int[] getNextPermutation(int[] currentPermutation) throws NoNextPermutationException {
  if (!hasNextPermutation(currentPermutation)) {
    throw new NoNextPermutationException();
  }

  int[] nextPermutation = Arrays.copyOf(currentPermutation, currentPermutation.length);
  int j = getFirstIndexGreaterThanItsSuccessorStartingBackwardsAtTheSecondLastIndex(currentPermutation);
  int k = getFirstGreaterSuccessorStartingBackwardsAtTheLastIndex(currentPermutation, j);
  swap(nextPermutation, j, k);
  sortingAllValuesAscendingStartingAtJ(nextPermutation, j);
  return nextPermutation;
}