title: How does this algorithm for generating the next lexicographically ordered permutation work?
body: <p>This is the step by step process I found for ordering lexicographical permutations: </p>
  
  <ol>
  <li><p>Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.</p></li>
  <li><p>Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’.</p></li>
  <li><p>Swap the two characters found in above 2 steps.</p></li>
  <li><p>Sort the substring (in non-decreasing order) after the original index of ‘first character’.</p></li>
  </ol>
  
  <p>Source: <a href="http://www.geeksforgeeks.org/lexicographic-permutations-of-string/" rel="nofollow">http://www.geeksforgeeks.org/lexicographic-permutations-of-string/</a></p>
  
  <p>I have already written my Pseudo-code for it,and am about to start programming it now as well. I understand what is happening in the Algorithm, but I am not sure why it works. Like on Step 2 why must the ceiling character be "the smallest character on right of ‘first character’, which is greater than ‘first character'". I understand that it doesn't work if you don't do it this way, but I don't understand why it does work when you do. </p>
  
  <p>If someone could explain to me why you need to each step in the algorithm that would be great and it would make me far more comfortable in starting my code.</p>
  
  <p>Edit: I should mention I understand why you rearange the substring into acsending order, as to find the smallest permute, what I dont understand is the step 1 and 2 as to why you swap the ceiling and the first charector</p>