title: Most efficient way to calculate lexicographic index
body: <p>Can anybody find any potentially more efficient algorithms for accomplishing the following task?:</p>
  
  <p>For any given permutation of the integers 0 thru 7, return the index which describes the permutation lexicographically (indexed from 0, not 1).</p>
  
  <p>For example,</p>
  
  <ul>
  <li>The array 0 1 2 3 4 5 6 7 should return an index of 0.</li>
  <li>The array 0 1 2 3 4 5 7 6 should return an index of 1.</li>
  <li>The array 0 1 2 3 4 6 5 7 should return an index of 2.</li>
  <li>The array 1 0 2 3 4 5 6 7 should return an index of 5039 (that's 7!-1 or <code>factorial(7)-1</code>).</li>
  <li>The array 7 6 5 4 3 2 1 0 should return an index of 40319 (that's 8!-1). This is the maximum possible return value.</li>
  </ul>
  
  <p>My current code looks like this:</p>
  
  <pre><code>int lexic_ix(int* A){
      int value = 0;
      for(int i=0 ; i&lt;7 ; i++){
          int x = A[i];
          for(int j=0 ; j&lt;i ; j++)
              if(A[j]&lt;A[i]) x--;
          value += x*factorial(7-i);  // actual unrolled version doesn't have a function call
      }
      return value;
  }
  </code></pre>
  
  <p>I'm wondering if there's any way I can reduce the number of operations by removing that inner loop, or if I can reduce conditional branching in any way (other than unrolling - my current code is actually an unrolled version of the above), or if there are any clever bitwise hacks or filthy C tricks to help.</p>
  
  <p>I already tried replacing</p>
  
  <pre><code>if(A[j]&lt;A[i]) x--;
  </code></pre>
  
  <p>with</p>
  
  <pre><code>x -= (A[j]&lt;A[i]);
  </code></pre>
  
  <p>and I also tried</p>
  
  <pre><code>x = A[j]&lt;A[i] ? x-1 : x;
  </code></pre>
  
  <p>Both replacements actually led to worse performance.</p>
  
  <p>And before anyone says it - YES this is a huge performance bottleneck: currently about 61% of the program's runtime is spent in this function, and NO, I don't want to have a table of precomputed values.</p>
  
  <p>Aside from those, any suggestions are welcome.</p>