Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

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
share|improve this question
    
Can we have more time until a winner is chosen? Three days is too little time. –  xnor Jul 22 at 3:34

5 Answers 5

up vote 4 down vote accepted

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.

share|improve this answer
    
Haha not quite what I was looking for when I said "without using factorials" but I suppose it counts. Kudos –  Kyle McCormick Jul 20 at 18:05

CJam, 31, with factorials

q~]{__(f<0+:+\,,(;1+:**\(;}h]:+
share|improve this answer
    
Why am I still getting upvote? The GolfScript answer can be rewritten in CJam with only 23 characters. –  user23013 Jul 20 at 14:59
4  
Because people like your answer. –  Sieg Jul 20 at 18:09

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.

share|improve this answer

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])
share|improve this answer

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,

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.