Permutation? Permutatino!

Question

Specifications

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.

Rules

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

Scoring:

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

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).

Answer 1

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).

Answer 2

05AB1E, 10 8 bytes

œ{ûD¹k<è

Try it online!

Explanation

œ{           # 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

Answer 3

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]

Answer 4

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

Unformatted

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).

Formatted

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];
  r.splice(t-1,2,v[i]);
  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.

Answer 5

Jelly, 8 - 50% = 4 bytes

Œ¿’»1œ?Ṣ

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.)

Explanation

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.

Œ¿’»1œ?Ṣ
Œ¿         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.

Variations

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.)

Answer 6

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(" ");
  console.log(input)
  num= input.length;
  document.getElementById("output").innerHTML=(f(num)(input));
}

<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!

Explanation:

while(--n>0&&a[n]>=a[n-1]);

Find the last location in the array that is not sorted

if(!n)return a;

If already sorted return

s=a.slice(--n);

Get everything starting from the point where it was not sorted

for(k=s.length;s[--k]>=a[n];);

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

t=a[n];s[0]=s[k];s[k]=t;

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!

Answer 7

Pip, 21 bytes

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

(YSSST*PMa^sy@?a-:1)

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

Explanation

                      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)

Answer 8

Ruby, 55 41 bytes

->a{x=a.permutation.sort;x[x.index(a)-1]}

Explanation:

• 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

Answer 9

Mathematica, 57 bytes

(a=Permutations@Sort@#)[[Max[1,Position[a,#][[1,1]]-1]]]&

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

Answer 10

Python 2, 73,81 bytes

s=s.split()
import itertools as i
x=sorted(list(i.permutations(s[1:],int(s[0]))))

Try it online!

Edit: Missed the lexicographical sort part of question.