Algorithm to find next greater permutation of a given string

by

Wikipedia has a nice article on lexicographical order generation. It also describes an algorithm to generate the next permutation.

Quoting:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

  1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
  2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
  3. Swap s[i] with s[j].
  4. Reverse the order of all of the elements after index i till the last element.

More Related Contents:

  1. Algorithm to beat Strassen’s Algorithm
  2. What does O(log n) mean exactly?
  3. HSL to RGB color conversion
  4. What exactly does big Ө notation represent?
  5. Select k random elements from a list whose elements have weights
  6. How are ssl certificates verified?
  7. How to find the intersection point between a line and a rectangle?
  8. Generate an integer that is not among four billion given ones
  9. Find duplicates in an array, without using any extra space
  10. How to generate Sudoku boards with unique solutions
  11. How to delete in a heap data structure?
  12. How can I detect common substrings in a list of strings
  13. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  14. Efficiently reverse the order of the words (not characters) in an array of characters
  15. Scheduling algorithm for a round-robin tournament?
  16. O(klogk) time algorithm to find kth smallest element from a binary heap
  17. Painter puzzle – estimation
  18. Approximate string matching algorithms
  19. Skip List vs. Binary Search Tree
  20. Previous power of 2
  21. Fast solution to Subset sum
  22. Generating shuffled range using a PRNG rather than shuffling
  23. Find out which combinations of numbers in a set add up to a given total
  24. Print the biggest K elements in a given heap in O(K*log(K))?
  25. Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location
  26. How do ASCII art image conversion algorithms work? [closed]
  27. Reason for the number 5381 in the DJB hash function?
  28. What is the best algorithm for finding the closest color in an array to another color? [closed]
  29. Quadratic algorithm for 4-SUM
  30. What is the algorithm that opencv uses for finding contours?

Leave a Comment