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.

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ But S_n is only cyclic for n<3 \$\endgroup\$ Commented Jul 14, 2017 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\$ Commented Jul 14, 2017 at 18:51
  • \$\begingroup\$ Would it suffice to only permute lists of 0's and1's? \$\endgroup\$ Commented Jul 14, 2017 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\$ Commented Jul 14, 2017 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\$ Commented Jul 14, 2017 at 22:13

11 Answers 11

Reset to default
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 }
Improve this answer
\$\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.

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

C++, 42 bytes

#include <algorithm> std::next_permutation

This exact operation is a builtin in C++.

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Why the space after #include? \$\endgroup\$ Commented Jul 16, 2017 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); }

Improve this answer
\$\endgroup\$
5
  • \$\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\$ Commented Jul 15, 2017 at 9:59
  • \$\begingroup\$ @Neil Good catch! \$\endgroup\$ Commented Jul 15, 2017 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\$ Commented Jul 15, 2017 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\$ Commented Jul 15, 2017 at 10:20
  • \$\begingroup\$ @Neil Thanks! Updated. (With 4 more bytes saved because we don't really need t to concat()). \$\endgroup\$ Commented Jul 15, 2017 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.
Improve this answer
\$\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; }
Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I think this is shorter as a function that permutes the list in-place. \$\endgroup\$ Commented Jul 15, 2017 at 9:23
  • \$\begingroup\$ I tried that, but exec gave me all kinds of errors in a function \$\endgroup\$ Commented Jul 15, 2017 at 15:05
0
\$\begingroup\$

Jelly, 10 bytes

ṢŒ!Q©i⁸‘ị®

Try it online!

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

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ @PeterTaylor I've fixed it. \$\endgroup\$ Commented Jul 14, 2017 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\$ Commented Jul 14, 2017 at 19:19
  • \$\begingroup\$ @EriktheOutgolfer it might be a bit messy for inputs that contain duplicates. \$\endgroup\$ Commented Jul 14, 2017 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\$ Commented Jul 14, 2017 at 19:23
0
\$\begingroup\$

05AB1E, 7 bytes

œêD¹k>è

Try it online!

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.