Your program must can take in an integer n, then take in n more strings (containing only alphanumeric characters) in your preferred method (separated by whitespace, file input, hash table etc.). You must then find the permutation before the inputted strings when sorted in lexicographical order, and output that in your preferred method.

If it is already sorted in lexicographical order, output the permutation in reverse regular lexicographical order.


  1. Code can be just a function

  2. If you pipe in from a file, you can to exclude the file name's length from your program (just the filename, not full path)

  3. If there are repeated characters, take the permutation before the first occurrence of the repeats

Test cases

3 abc hi def

The possible permutations of this (in lexicographical order) are:

abc def hi
abc hi def
def abc hi
def hi abc
hi abc def
hi def abc

Now see that abc hi def is the 2nd permutation, so we output abc def hi.

If instead we pick abc def hi(the first permutation), then output abc def hi.

Another test case is in the title: your function should map Permutation to Permutatino


The winner is the code with the smallest score, which is the length of the code multiplied by the bonus.


20% -90% (to keep non-esolangs in the fight) of your byte count if you can do this in O(N) time.

-50% (stacks with the above -90% to give a total of -95%) if your solution isn't O(N!) which is listing out permutations, finding the element and getting the index, subtracting 1 from the index (keep it the same if the index is 0) and outputting the element with the subtracted index

With the above 2 bonuses, I won't be surprised if there's a 2 byte answer.

Hint: there is definitely a faster way to do this apart from listing all the permutations and finding the supposed element in the general case

Congrats to @Forty3 for being the first person to get the O(N) solution!

Here's some (C based) pseudocode:

F(A) { // A[0..n-1] stores a permutation of {1, 2, .., n}
  int i, j;
  for (i = n - 1; i > 0 && (A[i-1] < A[i]); i--)
    ; // empty statement
  if (i = 0)
    return 0;
  for (j = i + 1; j < n && (A[i-1] > A[j]); j++)
    ; // empty statement
  swap(A[i-1], A[j-1]); // swap values in the two entries
  reverse(A[i..n-1]); // reverse entries in the subarray
  return 1;

If you want to test if your program is O(N), try with n=11 and the strings being the individual letters of Permutation. If it takes longer than a second, it's most definitely not O(N).

  • 1
    \$\begingroup\$ Can we get more test cases? \$\endgroup\$
    – Okx
    Commented Mar 28, 2017 at 11:06
  • \$\begingroup\$ @Okx If you test with the individual characters of the word "Permutation" and you get "Permutatino", then it's good. Of course, you have to wait about 5 hours if your solution isn't O(N). Other than that I'm a bit too lazy to add more test cases. \$\endgroup\$
    – Thunda
    Commented Mar 28, 2017 at 11:21
  • \$\begingroup\$ C++ has a linear time builtin for that but sadly even using that won't come close to a golfing language. Moreover: do you consider string compares to be a single step ? \$\endgroup\$
    – Christoph
    Commented Mar 28, 2017 at 11:38
  • \$\begingroup\$ Can we choose to only support char arrays as input, not string arrays? \$\endgroup\$
    – Okx
    Commented Mar 28, 2017 at 11:48
  • 4
    \$\begingroup\$ Things to avoid when writing challenges: Bonuses in code-golf \$\endgroup\$
    – mbomb007
    Commented Mar 28, 2017 at 13:37

10 Answers 10


Python 2, 118 96 - 50% = 48 bytes

Takes input in the form ['abc','def','ghi']. Note that this solution returns the list reversed if the input is sorted, as per a previous spec.

def f(n):m=n[1:];S=sorted;a=S(n);return[a.pop(a.index(n[0])-1)]+a[::-1]if m==S(m)else[n[0]]+f(m)

Try it Online!

Seems to be the O(n) solution more efficient than computing all permutations.

Explanation: Recursively checks if everything after the current element is in sorted order. If so, returns the string immediately lexicographically before (a.index(n[0])-1)) the first element + the rest of the list reversed (a[::-1]).

Runtime: O(n^2 logn) In the worst case (list is reversed), the function will call sorted, which has a runtime of nlogn, for each element in the list (n times).

  • \$\begingroup\$ I didn't count this specifically but I believe you can save 2 bytes by extracting sorted to a variable. You can also remove the unnecessary space between return [b]. Otherwise, nice solution! \$\endgroup\$
    – hyper-neutrino
    Commented Mar 28, 2017 at 5:47
  • \$\begingroup\$ What do you take as input? \$\endgroup\$ Commented Mar 28, 2017 at 7:00
  • 1
    \$\begingroup\$ Surely, sorted can't have a worst-case performance better than O(n log n) for large enough problem sizes. \$\endgroup\$ Commented Mar 28, 2017 at 10:54
  • \$\begingroup\$ Using sorted() definitely makes this non O(n) \$\endgroup\$ Commented Mar 28, 2017 at 10:58
  • \$\begingroup\$ If you can prove that this isn't O(N!) then you can have a -50% byte reduction. \$\endgroup\$
    – Thunda
    Commented Mar 28, 2017 at 12:19

05AB1E, 10 8 bytes


Try it online!


œ{           # get a list of sorted permutations of the input
  û          # append a reversed copy excepting the last element of the original
   D         # duplicate
    ¹k       # push the first index of the input in the list
      <      # decrement
       è     # index into the list with this
  • \$\begingroup\$ With esolang answers this short, I think I need to up the bonus for an O(n) solution. This is ridiculously slow. \$\endgroup\$
    – Thunda
    Commented Mar 28, 2017 at 10:46
  • \$\begingroup\$ @Thunda: Yeah. As it calculates all permutations, the computation time increases drastically the more strings there are in the input :P \$\endgroup\$
    – Emigna
    Commented Mar 28, 2017 at 11:38

Python 2, 83 bytes

-18 bytes, thanks to @Emigna

Takes strings without number as input. As rules were clarified, this is the solution.
Try it online

from itertools import*
def F(A):s=sorted(permutations(A))+[A];print s[s.index(A)-1]
  • \$\begingroup\$ To clarify, if the input string is ordered, it should output the input string \$\endgroup\$
    – Thunda
    Commented Mar 28, 2017 at 10:41
  • \$\begingroup\$ You could save 18 bytes like this \$\endgroup\$
    – Emigna
    Commented Mar 28, 2017 at 11:47
  • \$\begingroup\$ @Emigna Thank you, this is neat \$\endgroup\$ Commented Mar 28, 2017 at 12:13

JavaScript, 460 399 369 332 - 95% = 16.6 bytes


function f(n,v){var i=n-1,c=v[i],z="concat",y="slice",x="indexOf",w="reverse";for(;i>=0&&v[i]<=c;i--){c=v[i];}if(i==-1)return v;if(i==0){let s=v[z]().sort(),t=s[x](v[i])-1;return [s[t]][z]((s[y](0,t)[z](s[y](t+1)))[w]());}let p=v[y](0,i),r=v[y](i)[z]().sort()[w](),t=r[x](v[i])+1,m=r[t];r.splice(t-1,2,v[i]);return p[z]([m])[z](r);}

I am not convinced it is the O(n) solution but would appreciate if someone could take a quick glance and let me know. Also, I suspect there is some serious golfing which can be accomplished.. just haven't taken the time (yet).


function f2(n, v) {
  var i = n-1,c = v[i],z="concat",y="slice",x="indexOf",w="reverse";
  for ( ; i >= 0 && v[i] <= c; i--) {
    c = v[i];
  if (i == -1) return v;
  if (i == 0) {
    let s = v[z]().sort(), t = s[x](v[i]) - 1;
    return [s[t]][z]((s[y](0, t)[z](s[y](t + 1)))[w]());

  let p = v[y](0,i),
  r = v[y](i)[z]().sort()[w](),
  t = r[x](v[i])+1,
  m = r[t];
  return p[z]([m])[z](r);


Fiddle: https://jsfiddle.net/n2Lmswxf/8/

Edit 1 - whitespace and function name per @Emigna's suggestions.

Edit 2 - using some pointers from the link @Emigna suggested. If I ever found this code in a system I had to maintain, I would hunt the developer down and flog him.

Edit 3 - @Thunda - I hope it wasn't presumptuous to recalc the savings based on my latest golfing.

Edit 4 - Removed a sort and simplified the final reassembly logic.

  • 1
    \$\begingroup\$ Just removing the unnecessary whitespace and renaming the function to r saves 61 bytes. There are probably some tips from here that could help you save even more. \$\endgroup\$
    – Emigna
    Commented Mar 28, 2017 at 6:12
  • \$\begingroup\$ I just tried with 26 characters (the alphabet, obviously) and it's wayyyyyyyy faster than all the other answers. Great, it's O(N), it's pretty much the algorithm that I used. \$\endgroup\$
    – Thunda
    Commented Mar 28, 2017 at 12:50
  • \$\begingroup\$ Can you provide complexity of sort, used here? I might guess, that it is bigger, that O(N). @Thunda, you should not judge complexity by speed of evaluation. There is a definition for O-notation. \$\endgroup\$ Commented Mar 28, 2017 at 13:18
  • \$\begingroup\$ @DeadPossum It's definitely O(N) (as far as I can tell). It's a bunch of O(N) loops (and splice) with a couple O(1) functions sprinkled about. Could definitely do with an explanation though. If you go into the fiddle provided and copy paste a (ridiculous amount) of strings, then it would definitely be faster than the current best O(N^2 log n) solution. \$\endgroup\$
    – Thunda
    Commented Mar 28, 2017 at 13:21
  • 1
    \$\begingroup\$ @DeadPossum - So, O(n log n), then? \$\endgroup\$
    – Forty3
    Commented Mar 28, 2017 at 14:16

Jelly, 8 - 50% = 4 bytes


Try it online!

Runs in O(n log n) time. (This typically takes just over a second, due mostly to Jelly's startup time – the time of just over a second is true for both very short and fairly long inputs. There's some variation in how long it takes in TIO; the fastest I've observed is 0.914 real, 0.772 user, 0.121 system.)


Jelly actually has builtins for most of the challenge, but the way they're defined requires a sort. As far as I know, Jelly uses a comparison sort to sort lists of strings, which is what leads to the O(n log n) performance.

Œ¿         Find index of {the input} in a sorted list of its permutations
  ’        Decrement it
   »1      saturating from below at 1
     œ?    Find the nth permutation of
       Ṣ   the sorted input

Œ¿ is a builtin with an optimized implementation (i.e. not slower than O(n log n)); it doesn't do brute-forcing.


If wrap-around is allowed (it was under an earlier version of the spec), you can remove the »1 for a 6-byte solution and a score of 3. (Most of Jelly's builtins, including the relevant ones here, will naturally wrap around in the absence of other hints about what to do with an out-of-range value.)


JavaScript ES6, 170 - 95% = 8.5 bytes

f=n=>a=>{while(--n&&a[n]>=a[n-1]);if(!n)return a;s=a.slice(--n);for(k=s.length;s[--k]>=a[n];);t=a[n];s[0]=s[k];s[k]=t;return a.slice(0,n).concat(s[0],s.slice(1).reverse())}

function Permutatino() {
  input = document.getElementById("input").value.split(" ");
  num= input.length;
<input type="text" id="input" value="abc def ghi">
<button onclick="Permutatino()"> Run </button>
<pre id="output">

n=>a=>{while(--n&&a[n]>=a[n-1]);if(!n)return a;s=a.slice(--n);for(k=s.length;s[--k]>=a[n];);t=a[n];s[0]=s[k];s[k]=t;return a.slice(0,n).concat(s[0],s.slice(1).reverse())}

This code is a sequence of O(n) operations.

Try it online!



Find the last location in the array that is not sorted

if(!n)return a;

If already sorted return


Get everything starting from the point where it was not sorted


Find the index of the lexicographically closest element to the first element in the unsorted section which is lexicographically less than the first element.


Swap the first element with the found element.

return a.slice(0,n).concat(s[0],s.slice(1).reverse())

Return the first section of the array + the first element of the second section + the reversed remainder of the second section of the array.

Time complexity of operations:

slice() O(n)
concat() O(n)
reverse() O(n)
indexOf() O(n) //essentially what the for and while loops were

O(Nlog(N)) solution 143 - 50% = 71.5 bytes

n=>a=>{while(--n&&a[n]>=a[n-1]);if(!n)return a;s=a.slice(--n).sort();t=s.splice(s.indexOf(a[n])-1,1);return a.slice(0,n).concat(t,s.reverse())}

Try it online!

  • \$\begingroup\$ Nice solution - takes advantage of the fact that the "right" side of the array will always be in ascending order to start with and need only be reversed. Nicely done. \$\endgroup\$
    – Forty3
    Commented Mar 29, 2017 at 18:22

Pip, 21 bytes

20 bytes of code, +1 for -s flag.


Takes input as a single, space-delimited string on the command line. Try it online!


                      a is 1st cmdline arg; s is space (implicit)
                      Part 1:
         a^s           Split a on spaces
       PM              Get all permutations of a
    ST*                Map str() to each of them
                       Because of the -s flag, this joins each sublist on spaces
  SS                   Sort the list using string comparison
 Y                     Yank into the y variable
                      Part 2:
            y@?a       Find index of a in sorted list of permutations y
                -:1    Subtract 1 (using compute-and-assign for lower precedence than @?)
(                  )  Index into part 1 using part 2 (Pip's indexing is cyclical, which
                      takes care of the already-ordered-input case)
                      Print (implicit)

Ruby, 55 41 bytes



  • permutation.sort does exactly what is written on the box
  • find the original string
  • go back one step, if index is 0, wrap around to -1

Mathematica, 57 bytes


Anonymous function. Takes a list of strings as input and returns a list of strings as output.

  • \$\begingroup\$ Mathematica doesn't have built-ins for everything! \$\endgroup\$
    – Thunda
    Commented Mar 28, 2017 at 12:04

Python 2, 73,81 bytes

import itertools as i

Try it online!

Edit: Missed the lexicographical sort part of question.

  • 2
    \$\begingroup\$ Your solution should be function or full programm, so you need to specify input. Like s=input() or def f(s), etc. And it counts in bytes. \$\endgroup\$ Commented Mar 28, 2017 at 10:55
  • \$\begingroup\$ Also you missed part of question about sorting \$\endgroup\$ Commented Mar 28, 2017 at 10:57
  • \$\begingroup\$ My bad. Didnt notice that lexicographical order part. @DeadPossum Thanks. \$\endgroup\$ Commented Mar 28, 2017 at 11:25
  • 1
    \$\begingroup\$ If I use your header, it's supposed to output abc def hi instead of the permutations \$\endgroup\$
    – Thunda
    Commented Mar 28, 2017 at 11:29
  • \$\begingroup\$ Check on try it online ink I've shared along with answer! It does give the permutation sorted lexicographically. \$\endgroup\$ Commented Mar 28, 2017 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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