title: Generating permutations of a set (most efficiently)
body: <p>I would like to generate all permutations of a set (a collection), like so:</p>
  
  <pre><code>Collection: 1, 2, 3
  Permutations: {1, 2, 3}
                {1, 3, 2}
                {2, 1, 3}
                {2, 3, 1}
                {3, 1, 2}
                {3, 2, 1}
  </code></pre>
  
  <p>This isn't a question of "how", in general, but more about how most efficiently.
  Also, I wouldn't want to generate ALL permutations and return them, but only generating a single permutation, at a time, and continuing only if necessary (much like Iterators - which I've tried as well, but turned out to be less efficient).</p>
  
  <p>I've tested many algorithms and approaches and came up with this code, which is most efficient of those I tried:</p>
  
  <pre><code>public static bool NextPermutation&lt;T&gt;(T[] elements) where T : IComparable&lt;T&gt;
  {
      // More efficient to have a variable instead of accessing a property
      var count = elements.Length;
  
      // Indicates whether this is the last lexicographic permutation
      var done = true;
  
      // Go through the array from last to first
      for (var i = count - 1; i &gt; 0; i--)
      {
          var curr = elements[i];
  
          // Check if the current element is less than the one before it
          if (curr.CompareTo(elements[i - 1]) &lt; 0)
          {
              continue;
          }
  
          // An element bigger than the one before it has been found,
          // so this isn't the last lexicographic permutation.
          done = false;
  
          // Save the previous (bigger) element in a variable for more efficiency.
          var prev = elements[i - 1];
  
          // Have a variable to hold the index of the element to swap
          // with the previous element (the to-swap element would be
          // the smallest element that comes after the previous element
          // and is bigger than the previous element), initializing it
          // as the current index of the current item (curr).
          var currIndex = i;
  
          // Go through the array from the element after the current one to last
          for (var j = i + 1; j &lt; count; j++)
          {
              // Save into variable for more efficiency
              var tmp = elements[j];
  
              // Check if tmp suits the "next swap" conditions:
              // Smallest, but bigger than the "prev" element
              if (tmp.CompareTo(curr) &lt; 0 &amp;&amp; tmp.CompareTo(prev) &gt; 0)
              {
                  curr = tmp;
                  currIndex = j;
              }
          }
  
          // Swap the "prev" with the new "curr" (the swap-with element)
          elements[currIndex] = prev;
          elements[i - 1] = curr;
  
          // Reverse the order of the tail, in order to reset it's lexicographic order
          for (var j = count - 1; j &gt; i; j--, i++)
          {
              var tmp = elements[j];
              elements[j] = elements[i];
              elements[i] = tmp;
          }
  
          // Break since we have got the next permutation
          // The reason to have all the logic inside the loop is
          // to prevent the need of an extra variable indicating "i" when
          // the next needed swap is found (moving "i" outside the loop is a
          // bad practice, and isn't very readable, so I preferred not doing
          // that as well).
          break;
      }
  
      // Return whether this has been the last lexicographic permutation.
      return done;
  }
  </code></pre>
  
  <p>It's usage would be sending an array of elements, and getting back a boolean indicating whether this was the last lexicographical permutation or not, as well as having the array altered to the next permutation.</p>
  
  <p>Usage example:</p>
  
  <pre><code>var arr = new[] {1, 2, 3};
  
  PrintArray(arr);
  
  while (!NextPermutation(arr))
  {
      PrintArray(arr);
  }
  </code></pre>
  
  <p>The thing is that I'm not happy with the speed of the code.</p>
  
  <p>Iterating over all permutations of an array of size 11 takes about 4 seconds.
  Although it could be considered impressive, since the amount of possible permutations of a set of size 11 is <code>11!</code> which is nearly 40 million.</p>
  
  <p>Logically, with an array of size 12 it will take about 12 times more time, since <code>12!</code> is <code>11! * 12</code>, and with an array of size 13 it will take about 13 times more time than the time it took with size 12, and so on.</p>
  
  <p>So you can easily understand how with an array of size 12 and more, it really takes a very long time to go through all permutations.</p>
  
  <p>And I have a strong hunch that I can somehow cut that time by a lot (without switching to a language other than C# - because compiler optimization really does optimize pretty nicely, and I doubt I could optimize as good, manually, in Assembly).</p>
  
  <p>Does anyone know any other way to get that done faster?
  Do you have any idea as to how to make the current algorithm faster?</p>
  
  <p>Note that I don't want to use an external library or service in order to do that - I want to have the code itself and I want it to be as efficient as humanly possible.</p>