9
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Can we have more time until a winner is chosen? Three days is too little time. \$\endgroup\$ – xnor Jul 22 '14 at 3:34
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Haha not quite what I was looking for when I said "without using factorials" but I suppose it counts. Kudos \$\endgroup\$ – Kyle McCormick Jul 20 '14 at 18:05
4
\$\begingroup\$

CJam, 31, with factorials

q~]{__(f<0+:+\,,(;1+:**\(;}h]:+
\$\endgroup\$
  • \$\begingroup\$ Why am I still getting upvote? The GolfScript answer can be rewritten in CJam with only 23 characters. \$\endgroup\$ – jimmy23013 Jul 20 '14 at 14:59
  • 6
    \$\begingroup\$ Because people like your answer. \$\endgroup\$ – seequ Jul 20 '14 at 18:09
1
\$\begingroup\$

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,

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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])
\$\endgroup\$
0
\$\begingroup\$

J, 5 bytes (15 - 10)

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

This runs in O(n2) 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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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