27
\$\begingroup\$

Task

Your goal, should you choose to accept it, is to write a program, that, given an input string (or array of characters), outputs every possible permutation of the letters in that string. I'm finicky with my output, so it should be sorted alphabetically, with no duplicates.

Example:

Input: buzz

Output:

buzz
bzuz
bzzu
ubzz
uzbz
uzzb
zbuz
zbzu
zubz
zuzb
zzbu
zzub

Rules

  • This is so the shortest code wins.
  • Trailing spaces on each/any line are ok
  • A single newline after the last line is allowed (but no more)
\$\endgroup\$
  • \$\begingroup\$ Can output format be ["buzz" "bzuz" "bzzu" "ubzz" "uzbz" "uzzb" "zbuz" "zbzu" "zubz" "zuzb" "zzbu" "zzub"]? \$\endgroup\$ – Luis Mendo Nov 16 '16 at 1:00
  • \$\begingroup\$ Sorry, as I mentioned, I'm finicky ;) output must be on separate lines, rather than in a list format \$\endgroup\$ – Brian Gradin Nov 16 '16 at 1:03
  • \$\begingroup\$ Yes, that makes sense. I just wanted to see if I could remove one byte from my CJam answer (N* to p) :-) \$\endgroup\$ – Luis Mendo Nov 16 '16 at 1:04
  • 2
    \$\begingroup\$ A solid first challenge! \$\endgroup\$ – xnor Nov 16 '16 at 6:08
  • 1
    \$\begingroup\$ So many builtins! \$\endgroup\$ – Dan Nov 16 '16 at 11:27

29 Answers 29

23
\$\begingroup\$

Jelly, 5 bytes

ṢŒ!QY

Try it online!

Explanation

Ṣ         Sort
 Œ!       All permutations
   Q      Unique
    Y     Join by linefeeds
\$\endgroup\$
  • 26
    \$\begingroup\$ And... we have 100000 posts! Congrats! \$\endgroup\$ – ETHproductions Nov 16 '16 at 0:43
  • 1
    \$\begingroup\$ @ETHproductions Heh! Thanks! :-) \$\endgroup\$ – Luis Mendo Nov 16 '16 at 0:44
  • 1
    \$\begingroup\$ Congrats from my side as well :) @ETHproductions how did you get to that result? I am just curious... \$\endgroup\$ – geisterfurz007 Nov 16 '16 at 11:10
  • 5
    \$\begingroup\$ @geisterfurz007 Click the "share" link at the bottom of the post. That has ID of the post in the URL. \$\endgroup\$ – Martin Ender Nov 16 '16 at 12:16
  • 1
    \$\begingroup\$ Oh so it is the 100000th post of ppcg! I thought Luis Mendo was at that number already. My bad. Thanks for the explanation! \$\endgroup\$ – geisterfurz007 Nov 16 '16 at 12:32
12
\$\begingroup\$

05AB1E,  4  3 bytes

Updated, since an update to œ broke the old version,
which also saved a byte as suggested by Magic Octopus Urn.

œê»

Try it online!

Explanation

œ     # get all permutations of input
 ê    # sort and remove duplicates
  »   # join list by newlines
\$\endgroup\$
  • \$\begingroup\$ œê» is fine for non-legacy. \$\endgroup\$ – Magic Octopus Urn May 1 at 17:17
  • \$\begingroup\$ @MagicOctopusUrn: It is actually required for both versions as œ now returns a list of string in both. \$\endgroup\$ – Emigna May 2 at 19:53
10
\$\begingroup\$

MATL, 4 bytes

Y@Xu

Try it online!

Explanation

Y@    % Implicit input. Push 2D array of all permutations, each on a row, sorted
Xu    % Unique rows. Implicitly display
\$\endgroup\$
10
\$\begingroup\$

Python 3.5, 79 bytes

def f(s,w=''):
 s or print(w)
 for c in sorted({*s}):t=s*1;t.remove(c);f(t,w+c)

A function that takes input as a list of characters and outputs by printing.

Recursively makes every distinct permutation by taking each possible next character alphabetically out of the remaining distinct characters, and appending it to the output in progress w. Then, we recurse with this character removed. Once the input is emptied, we print w.

\$\endgroup\$
  • \$\begingroup\$ Take in a list of chars, not a string. \$\endgroup\$ – xnor Nov 17 '16 at 16:32
10
\$\begingroup\$

CJam, 5 bytes

Thanks to @EriktheOutgolfer for a correction (q instead of r)

qe!N*

Try it online!

Explanation

q        e# Read input as a string
 e!      e# Unique permutations, sorted
   N*    e# Join by newline. Implicitly display
\$\endgroup\$
8
\$\begingroup\$

Pyth - 5 bytes

jS{.p

Try it online here.

j        Join. Implictly joins on newlines.
 S       Sort
  {      Uniquify
   .p    All permutations, implicitly run on input.
\$\endgroup\$
  • \$\begingroup\$ Is S really needed? \$\endgroup\$ – Luis Mendo Nov 16 '16 at 0:50
  • \$\begingroup\$ @LuisMendo It's needed if the input isn't already sorted. \$\endgroup\$ – isaacg Nov 16 '16 at 0:54
  • 1
    \$\begingroup\$ @isaacg Thanks! I just realized I need that in my Jelly answer as well \$\endgroup\$ – Luis Mendo Nov 16 '16 at 0:58
  • \$\begingroup\$ @LuisMendo whoops. \$\endgroup\$ – Maltysen Nov 16 '16 at 1:12
6
\$\begingroup\$

Haskell, 46 bytes

import Data.List;unlines.sort.nub.permutations

2 bytes saved thanks to nimi

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need a name for the function, so you can drop the f=. \$\endgroup\$ – nimi Nov 16 '16 at 8:38
5
\$\begingroup\$

J, 19 bytes

/:~@~.@:{~!@#A.&i.#

Test case

   f =: /:~@~.@:{~!@#A.&i.#
   f 'buzz'
buzz
bzuz
bzzu
ubzz
uzbz
uzzb
zbuz
zbzu
zubz
zuzb
zzbu
zzub

Explanation

This is a 4-train:

                     /- ~ --- /:
               /- @ -^- ~.
  /- ~ --- @: -^- {
  |
  |            /- !
--<     /- @ --^- #
  |     |
  \-----<      /- A.
        >- & --^- i.
        \- #

Basically:

/:~@~.@:{~!@#A.&i.#
          !  A.&     get permutations
           @#   i.#  of range (0..length)
        {~           map indices to chars in string
      @:             then
    ~.               unique
   @                 then
/:~                  sort
\$\endgroup\$
  • \$\begingroup\$ I think [:~.i.@!@#A./:~ should save you a few bytes \$\endgroup\$ – miles Dec 24 '16 at 23:00
4
\$\begingroup\$

JavaScript (Firefox 30+), 129 124 bytes

f=(a,i=-1)=>a[1]?[for(x of a.sort())if(a.indexOf(x)==++i)f([...a.slice(0,i),...a.slice(i+1)]).replace(/^/gm,x)].join`
`:a[0]

Not too bad for a language with no permutation built-ins...

\$\endgroup\$
  • \$\begingroup\$ I converted this to operate on strings; despite taking 23 bytes just to sort the characters into order I still got the job done in 120 bytes. \$\endgroup\$ – Neil Nov 16 '16 at 11:02
3
\$\begingroup\$

Python 3.5, 81 bytes:

from itertools import*;lambda i:'\n'.join(sorted({*map(''.join,permutations(i))}))

Really...81 bytes when the next longest answer is 48 bytes...sigh. Well, I will try this golf this more as much as I can, but golfing tips are still very much appreciated.

Also, here is the shortest solution I could get in Python 2 at 86 bytes:

from itertools import*;lambda f:'\n'.join(sorted({''.join(i)for i in permutations(f)}))

Apparently in Python 2, [*...] returns a Syntax Error, and since permutations returns itertools.permutations object at 0x..., the next shortest way (that I know) of extracting the unique permutations is using {''.join(i)for i in permutations(f)} where f is the input string.

Finally, note that these are both lambda functions and thus must be called in the format print(<Function Name>(<Input String>)).

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 34 23 bytes

Print@@@Permutations@#&

The input must be a list of characters.

Explanation

Permutations@

Find all permutations of the input, sorted and duplicate-free.

Print@@@

Print them one by one.

\$\endgroup\$
3
\$\begingroup\$

Brachylog, 9 bytes

:pfdo~@nw

Try it online!

Explanation

:pf         Find all outputs of p - Permute with the main Input as input
   d        Remove Duplicates
    o       Order
     ~@n    Concatenate into a single string with linebreaks as separator
        w   Write to STDOUT
\$\endgroup\$
3
\$\begingroup\$

Perl 6,  49  44 bytes

String as input

*.comb.permutations.sort».join.squish.map: *.put

List of characters as input

*.permutations.sort».join.squish.map: *.put

Expanded

*\              # Whatever lambda
# .comb\        # split into a list of characters
.permutations\  # returns a list of lists
.sort\
».join\         # join the second level lists
.squish\        # remove adjacent repeated values
.map: *.put     # print each on its own line
\$\endgroup\$
  • 2
    \$\begingroup\$ every time I see perl 6 code I wonder why I haven't installed it yet \$\endgroup\$ – Gabriel Benamy Nov 17 '16 at 1:48
  • \$\begingroup\$ @GabrielBenamy There is an irc bot that runs Perl 6 code on the freenode.net #perl6 channel. \$\endgroup\$ – Brad Gilbert b2gills Nov 18 '16 at 21:13
  • \$\begingroup\$ You can do ».say instead of .map: *.put \$\endgroup\$ – Jo King Jul 30 '18 at 23:10
  • 1
    \$\begingroup\$ @JoKing Technically ».say is allowed to do them in any order, and at one time it was purposely done out of order. \$\endgroup\$ – Brad Gilbert b2gills Aug 1 '18 at 17:35
3
\$\begingroup\$

Brachylog (v2), 5 bytes

pᵘoẉᵐ

Try it online!

Find nique permutations of input, sort them, ap riteln (write with newline) over that array.

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

Python 3, 77 85 bytes

Now sorts!

import itertools as i
for a in sorted(set(i.permutations(input()))):print("".join(a))
\$\endgroup\$
  • 1
    \$\begingroup\$ To shorten this, you could do from itertools import* as opposed to import itertools as i. You'd be able to save a byte by replacing i.permutations by permutations. \$\endgroup\$ – 0WJYxW9FMN Nov 16 '16 at 20:50
  • \$\begingroup\$ Using {*...} instead of set(...) saves you two more bytes. \$\endgroup\$ – movatica Apr 30 at 21:04
2
\$\begingroup\$

PowerShell v3+, 171 bytes

param([char[]]$x)$a,$b=$x;$a=,$a;while($b){$z,$b=$b;$a+=$a|%{0..($y=($c="$_").Length)|%{-join($c[0..$_]+$z+$c[++$_..$y])};"$z$c";"$c$z"}}$a|?{$_.length-eq$x.count}|sort -u

PowerShell v3 introduced the -Unique flag on the Sort-Object cmdlet, so it's a few bytes shorter than the below v2 version, since we don't need to Select first.

v2 version, 178 bytes:

param([char[]]$x)$a,$b=$x;$a=,$a;while($b){$z,$b=$b;$a+=$a|%{0..($y=($c="$_").Length)|%{-join($c[0..$_]+$z+$c[++$_..$y])};"$z$c";"$c$z"}}$a|?{$_.length-eq$x.count}|select -u|sort

PowerShell doesn't have any built-in permutations, so I borrowed my code from Prime Factors Buddies and slightly tweaked it for use here.

This is essentially three portions, which I'll expand on below.

param([char[]]$x)$a,$b=$x;$a=,$a Takes input $x, casts it as a char-array, strips off the first letter into $a and the rest into $b, and then recasts $a as an array with the comma-operator.

while($b){$z,$b=$b;$a+=$a|%{0..($y=($c="$_").Length)|%{-join($c[0..$_]+$z+$c[++$_..$y])};"$z$c";"$c$z"}} Loops through the remaining letters ($b), each iteration taking the next letter and storing it into $z and leaving the remaining in $b, then array-concatenating onto $a the result of sending $a through its own loop -- each item of $a (temporarily stored into $c) is looped over its own .length, and then $z is inserted into every position, including prepending and appending with $z$c and $c$z. For example, for $c = '12' and $z = '3', this will result in '132','312','123' being concatenated back into $a.

The final portion $a|?{$_.length-eq$x.count}|select -u|sort takes each element of $a and uses Where-Object clause to filter out only those that have the same length as the input string, then selects only the -unique items, and finally sorts those alphabetically. The resulting strings are all left on the pipeline, and output via implicit Write-Output happens at program completion.

PS C:\Tools\Scripts\golfing> .\alphabetically-permute-a-string.ps1 'PPCG'
CGPP
CPGP
CPPG
GCPP
GPCP
GPPC
PCGP
PCPG
PGCP
PGPC
PPCG
PPGC
\$\endgroup\$
  • \$\begingroup\$ If you are willing to go 3.0 You can change |select -u|sort to |sort -u. Pretty sure 2.0 does not have that. \$\endgroup\$ – Matt Nov 16 '16 at 19:58
  • \$\begingroup\$ @Matt Thanks - you're correct. That was introduced in v3. \$\endgroup\$ – AdmBorkBork Nov 16 '16 at 21:32
2
\$\begingroup\$

JavaScript (ES6), 119 bytes

f=(s,t=[...s].sort().join``,p=``)=>t?t.replace(/./g,(c,i)=>t.indexOf(c)==i?f(s,t.slice(0,i)+t.slice(i+1),p+c):``):p+`\n`

Where \n represents the literal newline character. Port of @ETHproduction's answer to use strings instead of arrays. Reversing the output, or moving the trailing newline to the beginning, saves 3 bytes.

\$\endgroup\$
1
\$\begingroup\$

R, 113 bytes

x=scan(,"");cat(sort(unique(apply(matrix(x[permute:::allPerms(l<-length(x))],,l),1,paste,collapse=""))),sep="\n")

Reads input from stdin. The permute package is assumed to be installed in order to call the allPerms function.

Will add an explanation as I get home from work.

\$\endgroup\$
1
\$\begingroup\$

Java 302 300 bytes

import java.util.*;class M{public static void main(String[]a){for(Object s:p(new TreeSet(),"",a[0]))System.out.println(s);}static Set p(Set l,String p,String s){int n=s.length(),i=0;if(n>1)for(;i<n;p(l,p+s.charAt(i),s.substring(0,i)+s.substring(++i,n)));else if(!l.contains(p+=s))l.add(p);return l;}}

Ungolfed & test code:

Try it here.

import java.util.*;
class M{
  static Set p(Set l, String p, String s){
    int n = s.length(),
        i = 0;
    if(n > 1){
      for(; i < n; p(l, p + s.charAt(i), s.substring(0, i) + s.substring(++i, n)));
    } else if(!l.contains(p+=s)){
      l.add(p);
    }
    return l;
  }

  public static void main(String[] a){
    for(Object s : p(new TreeSet(), "", a[0])){
      System.out.println(s);
    }
  }
}

Input: test
Output:

estt
etst
etts
sett
stet
stte
test
tets
tset
tste
ttes
ttse
\$\endgroup\$
  • 1
    \$\begingroup\$ The permutations are supposed to be alphabetically sorted \$\endgroup\$ – Ikaros Nov 16 '16 at 13:53
  • \$\begingroup\$ @Ikaros Thanks, should be fixed now. \$\endgroup\$ – Kevin Cruijssen Nov 16 '16 at 14:06
1
\$\begingroup\$

Racket 82 bytes

(sort(remove-duplicates(map list->string(permutations(string->list s)))) string<?)

Ungolfed:

(define(f s)
 (sort
  (remove-duplicates
   (map
    list->string
    (permutations
     (string->list s))))
  string<?))

Testing:

(f "buzz")

Ouput:

'("buzz" "bzuz" "bzzu" "ubzz" "uzbz" "uzzb" "zbuz" "zbzu" "zubz" "zuzb" "zzbu" "zzub")
\$\endgroup\$
0
\$\begingroup\$

Groovy, 69 Bytes

{(it as List).permutations().unique().sort().each{println it.join()}}
\$\endgroup\$
0
\$\begingroup\$

Ruby, 51 bytes

->s{puts s.chars.permutation.map(&:join).uniq.sort}
\$\endgroup\$
  • \$\begingroup\$ how to we can run it? \$\endgroup\$ – بارپابابا Nov 17 '16 at 5:51
  • \$\begingroup\$ puts s.chars.permutation().map(&:join).uniq 43 Byte \$\endgroup\$ – بارپابابا Nov 17 '16 at 5:59
  • \$\begingroup\$ That doesn't work. You need to sort the output, and you can't refer to s without prior definition. \$\endgroup\$ – Lee W Nov 17 '16 at 15:36
0
\$\begingroup\$

Actually, 8 bytes

Golfing suggestions welcome! Try it online!

;l@╨♂Σ╔i

Ungolfing

     Implicit input s.
;l   Get len(s).
@╨   Get all len(s)-length permutations of s.
♂Σ   Sum them all back into strings.
╔    uniq() the list of strings.
i    Flatten the list of strings.
     Implicit print the stack, separated by newlines.
\$\endgroup\$
0
\$\begingroup\$

Pip, 8 bytes

7 bytes of code, +1 for -n flag.

SSUQPMa

Takes a string as a command-line argument. Try it online!

Pip's scanner breaks runs of uppercase letters into two-letter chunks. So this code is SS UQ PM a--i.e. SortString(UniQue(PerMutations(a))), with a being the command-line arg. The -n flag ensures the result list is newline-separated. That's all there is to it.

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

K (oK), 14 bytes

Solution:

?x@<x@:prm@#x:

Try it online!

Explanation:

Use the built-in permutation function, prm, to generate permutations of length of the input, apply these permutations to the input, sort alphabetically and then take distinct values.

?x@<x@:prm@#x: / the solution
            x: / store input as x
           #   / count length of x
       prm@    / apply (@) function prm
    x@:        / apply indices to x and save result back into x
   <           / indices to sort ascending
 x@            / apply to x
?              / take distint
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -MList::Util=uniq -F, 68 bytes

$"=',';@b=sort@F;map{say if"@b"eq join$",sort/./g}uniq glob"{@b}"x@b

Try it online!

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

Japt v2.0a0 -R, 5 bytes

á â n

Try it

\$\endgroup\$
  • \$\begingroup\$ û is the centre pas method; I think you meant n ;) \$\endgroup\$ – Shaggy Apr 29 at 9:19
  • \$\begingroup\$ @Shaggy I just put sort in the searchbar in your interpreter and clicked the first one I found. But á seems to give each permutation in alphabetic order already \$\endgroup\$ – Embodiment of Ignorance Apr 30 at 2:25
  • \$\begingroup\$ Oop, that's a typo; should be ü. I'll fix it tomorrow. The permutations of "buzz" happen to be sorted because the word itself is - try it with "zzub" instead, for example. \$\endgroup\$ – Shaggy Apr 30 at 19:17
  • \$\begingroup\$ @Shaggy, I see, updated answer with n (it's easier to type) \$\endgroup\$ – Embodiment of Ignorance Apr 30 at 20:00
0
\$\begingroup\$

C++ (gcc), 132 128 bytes

#include<bits/stdc++.h>
using namespace std;int main(){string s;for(cin>>s;cout<<s<<endl,next_permutation(s.begin(),s.end()););}

Try it online!

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

Clam, 9 bytes

p_D`Sq@~Q

Explanation

          - Implicit Q = first input
p         - Print...
 _        - Sorted ascending value (alphabetical order)
  D       - Distinct from...
   `Sq    - Joined (map(q=>q.join(""))
      @~Q - Permutations of Q
\$\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.