Permutation Numbering

Question

The Challenge

For a given set of n integers, write a program which will output its lexicographic index.

The Rules

• The input must only be a set of unique non-negative integers separated by spaces.
• You should output the lexicographic index (range 0 to n!-1 inclusive) of the permutation.
• No permutation libraries or permutation built-ins may be used.
• You may not generate the set of permutations or any subset of permutations of the input to help you find the index.
• You also can't increment or decrement the given permutation to the next/previous(lexicographically) permutation.
• Bonus points (-10 bytes) if you find some way to complete this without using factorials.
• Runtime should be less than 1 minute for n = 100
• Shortest code by byte count wins
• Winner chosen Tuesday (July 22, 2014)

More About Permutations

• http://www.monkeyphysics.com/articles/read/26/numbering_permutations.html
• Permutation group operation
• http://lin-ear-th-inking.blogspot.com/2012/11/enumerating-permutations-using.html

Examples

0 1 2 --> 0
0 2 1 --> 1
1 0 2 --> 2
1 2 0 --> 3
2 0 1 --> 4
2 1 0 --> 5
0 1 2 3 4 5 6 7 --> 0
0 1 2 3 4 5 7 6 --> 1
0 1 2 3 4 6 5 7 --> 2
1 3 5 17        --> 0
781 780 779 13  --> 23
81 62 19 12 11 8 2 0 --> 40319
195 124 719 1 51 6 3 --> 4181

Answer 1

GolfScript, 12 (22 characters - 10 bonus)

~]0\.,{.,@*\.(@$?@+\}*

Bonus points for not using factorials. Input must be given on STDIN in the format desriped in the question. You can try the code online.

Answer 2

CJam, 31, with factorials

q~]{__(f<0+:+\,,(;1+:**\(;}h]:+

Answer 3

Cobra - 202

Obviously Cobra isn't really competing in this one.

class P
    var n=0
    var t=CobraCore.commandLineArgs[1:]
    def main
        .f(.t[0:0])
    def f(l as List<of String>)
        if.t.count==l.count,print if(.t<>l,'',.n+=1)
        else,for i in.t.sorted,if i not in l,.f(l+[i])

Answer 4

Python 2 (77 = 87-10)

p=map(int,raw_input().split())
s=0
while p:s=s*len(p)+sorted(p).index(p.pop(0))
print s

Such readable. Much built-in. Wow.

We use the fact that the lexicographic index of a permutation is the sum over the elements of the permutations of the number of inversions above that element (values after it but below it) multiplied by the factorial of the number of elements after it. Rather than evaluate this polynomial-like expression term by term, we use something akin to Horner's method.

Rather then looping over array indices, we repeatedly remove the first element of the list and process the remaining elements. The expression sorted(p).index(p.pop(0)) counts the number of inversions past the first index by taking its position in the sorted list, while at the same time doing the removal.

Sadly, I had to use Python 2 and take 4 more characters for raw_input (though -1 for print) because in Python 3 the map(int,...) produces a map object, which doesn't support list operations,

Answer 5

Pyth (13 = 23-10)

JVPwdWJ=Z+*ZlJXovNJ;J)Z

A port of my Python answer.

A Python translation (with some irrelevant stuff filtered out):

Z=0
J=rev(split(input()," "))
while J:
 Z=plus(times(Z,len(J)),index(order(lambda N:eval(N),J),J.pop()))
print(Z)

The input numbers stay strings but are sorted as ints by using eval as the key. The list is reversed so that pop takes the the front rather than the back.

Answer 6

J, 5 bytes (15 - 10)

#\.#.+/@(<{.)\.

This runs in O(n²) time and is able to handle n = 100 easily.

Usage

   f =: #\.#.+/@(<{.)\.
   f 0 1 2
0
   f 0 2 1
1
   f 1 0 2
2
   f 1 2 0
3
   f 2 0 1
4
   f 2 1 0
5
   f 0 1 2 3 4 5 6 7
0
   f 0 1 2 3 4 5 7 6
1
   f 0 1 2 3 4 6 5 7
2
   f 1 3 5 17
0
   f 781 780 779 13
23
   f 81 62 19 12 11 8 2 0
40319
   f 195 124 719 1 51 6 3
4181
   NB. A. is the builtin for permutation indexing
   timex 'r =: f 927 A. i. 100'
0.000161
   r
927

Explanation

#\.#.+/@(<{.)\.  Input: array P
             \.  For each suffix of P
          {.       Take the head
         <         Test if it is greater than each of that suffix
     +/@           Sum, count the number of times it is greater
#\.              Get the length of each suffix of P
   #.            Convert to decimal using a mixed radix