8
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Can we get more test cases? \$\endgroup\$ – Okx Mar 28 '17 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 Mar 28 '17 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 Mar 28 '17 at 11:38
  • \$\begingroup\$ Can we choose to only support char arrays as input, not string arrays? \$\endgroup\$ – Okx Mar 28 '17 at 11:48
  • 4
    \$\begingroup\$ Things to avoid when writing challenges: Bonuses in code-golf \$\endgroup\$ – mbomb007 Mar 28 '17 at 13:37

10 Answers 10

4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\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\$ – HyperNeutrino Mar 28 '17 at 5:47
  • \$\begingroup\$ What do you take as input? \$\endgroup\$ – Dead Possum Mar 28 '17 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\$ – LegionMammal978 Mar 28 '17 at 10:54
  • \$\begingroup\$ Using sorted() definitely makes this non O(n) \$\endgroup\$ – Dead Possum Mar 28 '17 at 10:58
  • \$\begingroup\$ If you can prove that this isn't O(N!) then you can have a -50% byte reduction. \$\endgroup\$ – Thunda Mar 28 '17 at 12:19
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\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 Mar 28 '17 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 Mar 28 '17 at 11:38
2
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ To clarify, if the input string is ordered, it should output the input string \$\endgroup\$ – Thunda Mar 28 '17 at 10:41
  • \$\begingroup\$ You could save 18 bytes like this \$\endgroup\$ – Emigna Mar 28 '17 at 11:47
  • \$\begingroup\$ @Emigna Thank you, this is neat \$\endgroup\$ – Dead Possum Mar 28 '17 at 12:13
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 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 Mar 28 '17 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 Mar 28 '17 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\$ – Dead Possum Mar 28 '17 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 Mar 28 '17 at 13:21
  • 1
    \$\begingroup\$ @DeadPossum - So, O(n log n), then? \$\endgroup\$ – Forty3 Mar 28 '17 at 14:16
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\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 Mar 29 '17 at 18:22
1
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Mathematica doesn't have built-ins for everything! \$\endgroup\$ – Thunda Mar 28 '17 at 12:04
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 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\$ – Dead Possum Mar 28 '17 at 10:55
  • \$\begingroup\$ Also you missed part of question about sorting \$\endgroup\$ – Dead Possum Mar 28 '17 at 10:57
  • \$\begingroup\$ My bad. Didnt notice that lexicographical order part. @DeadPossum Thanks. \$\endgroup\$ – Keerthana Prabhakaran Mar 28 '17 at 11:25
  • 1
    \$\begingroup\$ If I use your header, it's supposed to output abc def hi instead of the permutations \$\endgroup\$ – Thunda Mar 28 '17 at 11:29
  • \$\begingroup\$ Check on try it online ink I've shared along with answer! It does give the permutation sorted lexicographically. \$\endgroup\$ – Keerthana Prabhakaran Mar 28 '17 at 11:51

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.