9
\$\begingroup\$

For this challenge you are going to make a function (your function may be a complete program) that takes a list as input and returns a permutation of that list. Your function must obey the following requirements.

  • It must be deterministic.

  • Composing your function with itself a variable number of times should be capable of getting a list to any of its permutations.

This is a code-golf question so answers will be scored in bytes, with less bytes being better.

Further rules

  • You may take any type of list, ([Integer],[String],[[Integer]]) as long as it

    • Can be non empty
    • Can contain distinct objects with at least 16 possible values. (You can't use a Haskell [()] and claim your function is id)
    • Can contain duplicate objects (no sets)
  • You may write a program or a function, but must obey standard IO.

\$\endgroup\$
  • \$\begingroup\$ But S_n is only cyclic for n<3 \$\endgroup\$ – Leaky Nun Jul 14 '17 at 18:51
  • \$\begingroup\$ @LeakyNun, it's not asking for a single permutation which generates the symmetric group: it's asking for a next_permutation function. \$\endgroup\$ – Peter Taylor Jul 14 '17 at 18:51
  • \$\begingroup\$ Would it suffice to only permute lists of 0's and1's? \$\endgroup\$ – xnor Jul 14 '17 at 19:59
  • \$\begingroup\$ I'm not sure I understand the point of this restriction. If you allow lists of Booleans, what's the point of not allowing iterables over any two distinct items? \$\endgroup\$ – Dennis Jul 14 '17 at 22:11
  • \$\begingroup\$ @Dennis You make a good point. I will disallowed lists of booleans. Or types that have less than 16 possible values. \$\endgroup\$ – Sriotchilism O'Zaic Jul 14 '17 at 22:13

11 Answers 11

4
\$\begingroup\$

CJam (11 bytes)

{_e!_@a#(=}

Online demo showing the full cycle for a four-element list with one duplicate element.

Dissection

{      e# Define a block
  _e!  e#   Find all permutations of the input. Note that if there are duplicate
       e#   elements in the input then only distinct permutations are produced.
       e#   Note also that the permutations are always generated in lexicographic
       e#   order, so the order is independent of the input.
  _@a# e#   Find the index of the input in the list
  (=   e#   Decrement and get the corresponding element of the list
       e#   Incrementing would also have worked, but indexing by -1 feels less
       e#   wrong than indexing by the length, and makes this more portable to
       e#   GolfScript if it ever adds a "permutations" built-in
}
\$\endgroup\$
2
\$\begingroup\$

Mathematica + Combinatorica (Built-in Package) 34 Bytes

19 bytes to load the package and 15 for the function.

<<"Combinatorica`";NextPermutation

Usage:

%@{c, b, a}

Without the built-in, 61 Bytes

Extract[s=Permutations[Sort@#],Mod[s~Position~#+1,Length@s]]&

Combinatorica is supposed to be fully incorporated into Mathematica, but I think the NextPermutation function was overlooked.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 90 bytes

from itertools import*
def f(l):p=[*permutations(sorted(l))];return p[-~p.index(l)%len(p)]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C++, 42 bytes

#include <algorithm>
std::next_permutation

This exact operation is a builtin in C++.

\$\endgroup\$
  • 2
    \$\begingroup\$ Why the space after #include? \$\endgroup\$ – Yytsi Jul 16 '17 at 16:15
2
\$\begingroup\$

JavaScript (ES6), 145 139 137 134 108 bytes

Saved a whopping 25 bytes thanks to @Neil!

Takes input as an array of alphabetical characters. Returns the next permutation as another array.

a=>(t=x=y=-1,a.map((v,i)=>v<a[i+1]?(t=v,x=i):y=i>x&v>t?i:y),a[x]=a[y],a[y]=t,a.concat(a.splice(x+1).sort()))

How?

This is a generation in lexicographic order that processes the 4 following steps at each iteration:

  1. Find the largest index X such that a[X] < a[X+1]

    a.map((v, i) => v < a[i + 1] ? (t = v, x = i) : ...)
    
  2. Find the largest index Y greater than X such that a[Y] > a[X]

    a.map((v, i) => v < a[i + 1] ? ... : y = i > x & v > t ? i : y)
    
  3. Swap the value of a[X] with that of a[Y]

    a[x] = a[y], a[y] = t
    
  4. Sort the sequence from a[X + 1] up to and including the final element, in ascending lexicographic order

    a.concat(a.splice(x + 1).sort())
    

Example:

steps

Demo

let f =

a=>(t=x=y=-1,a.map((v,i)=>v<a[i+1]?(t=v,x=i):y=i>x&v>t?i:y),a[x]=a[y],a[y]=t,a.concat(a.splice(x+1).sort()))

for(a = ["A", "B", "C", "D"], n = 0; n < 25; n++) {
  console.log(a.join(','));
  a = f(a);
}

\$\endgroup\$
  • \$\begingroup\$ Can't you sort rather than reversing? Also I think v<a[i+1]&&(t=v,x=i) saves a byte, and you might be able to make more savings using splice instead of two slices. \$\endgroup\$ – Neil Jul 15 '17 at 9:59
  • \$\begingroup\$ @Neil Good catch! \$\endgroup\$ – Arnauld Jul 15 '17 at 10:07
  • \$\begingroup\$ I think I was able to merge the two maps as well, for 112 bytes: a=>(t=x=y=-1,a.map((v,i)=>v<a[i+1]?(t=v,x=i):y=i>x&v>t?i:y),a[x]=a[y],a[y]=t,t=a.splice(++x).sort(),a.concat(t)) \$\endgroup\$ – Neil Jul 15 '17 at 10:09
  • \$\begingroup\$ I have to admit I didn't think a.concat(a.splice(++x).sort()) was going to work otherwise I would have tried it... \$\endgroup\$ – Neil Jul 15 '17 at 10:20
  • \$\begingroup\$ @Neil Thanks! Updated. (With 4 more bytes saved because we don't really need t to concat()). \$\endgroup\$ – Arnauld Jul 15 '17 at 10:21
1
\$\begingroup\$

Jelly, 6 bytes

Œ¿’œ?Ṣ

Cycles through the permutations in descending lexicographical order.

Try it online!

How it works

Œ¿’œ?Ṣ  Main link. Argument: A (array)

Œ¿      Compute the permutation index n of A, i.e., the index of A in the
        lexicographically sorted list of permutations of A.
  ’     Decrement the index by 1, yielding n-1.
     Ṣ  Sort A.
   œ?   Getthe (n-1)-th permutation of sorted A.
\$\endgroup\$
1
\$\begingroup\$

C, 161 bytes

Actual O(n) algorithm.

#define S(x,y){t=x;x=y;y=t;}
P(a,n,i,j,t)int*a;{for(i=n;--i&&a[i-1]>a[i];);for(j=n;i&&a[--j]<=a[i-1];);if(i)S(a[i-1],a[j])for(j=0;j++<n-i>>1;)S(a[i+j-1],a[n-j])}

Example usage:

int main(int argc, char** argv) {
    int i;
    int a[] = {1, 2, 3, 4};

    for (i = 0; i < 25; ++i) {
        printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
        P(a, 4);
    }

    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

Python 2, 154 bytes

x=input()
try:exec'%s=max(k for k in range(%s,len(x))if x[%s-1]<x[k]);'*2%tuple('i1kjii');x[i-1],x[j]=x[j],x[i-1];x[i:]=x[:i-1:-1]
except:x.sort()
print x

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I think this is shorter as a function that permutes the list in-place. \$\endgroup\$ – orlp Jul 15 '17 at 9:23
  • \$\begingroup\$ I tried that, but exec gave me all kinds of errors in a function \$\endgroup\$ – Dennis Jul 15 '17 at 15:05
0
\$\begingroup\$

Jelly, 10 bytes

ṢŒ!Q©i⁸‘ị®

Try it online!

Sort > all permutation > find input > add 1 > index into "all permutation

\$\endgroup\$
  • \$\begingroup\$ @PeterTaylor I've fixed it. \$\endgroup\$ – Leaky Nun Jul 14 '17 at 19:02
  • \$\begingroup\$ There are specific builtins for permutations (i.e. you can just do Œ¿‘œ?Ṣ). I didn't feel like stealing since, well, same algo. \$\endgroup\$ – Erik the Outgolfer Jul 14 '17 at 19:19
  • \$\begingroup\$ @EriktheOutgolfer it might be a bit messy for inputs that contain duplicates. \$\endgroup\$ – Leaky Nun Jul 14 '17 at 19:21
  • \$\begingroup\$ Hmm...I guess so, I had a version which did work for that previously but you seem to use the Q thingy. You can still golf to ṢŒ!Qµi³‘ị. \$\endgroup\$ – Erik the Outgolfer Jul 14 '17 at 19:23
0
\$\begingroup\$

05AB1E, 7 bytes

œêD¹k>è

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PHP, 117 bytes

Takes input/output as string list of lower letters

$a=str_split($s=$argn);rsort($a);if(join($a)!=$s)for($n=$s;($c=count_chars)(++$n)!=$c($s););else$n=strrev($s);echo$n;

Try it online!

\$\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.