Alphabetically permute a string

Question

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 code-golf 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)

Answer 1

Jelly, 5 bytes

ṢŒ!QY

Try it online!

Explanation

Ṣ         Sort
 Œ!       All permutations
   Q      Unique
    Y     Join by linefeeds

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

Haskell, 46 bytes

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

2 bytes saved thanks to nimi

Answer 8

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

Answer 9

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

Answer 10

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.

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

Brachylog (v2), 5 bytes

pᵘoẉᵐ

Try it online!

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

Answer 15

Python 3, 77 85 bytes

Now sorts!

import itertools as i
for a in sorted(set(i.permutations(input()))):print("".join(a))

Answer 16

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

Answer 17

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.

Answer 18

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.

Answer 19

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

Answer 20

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

Answer 21

Groovy, 69 Bytes

{(it as List).permutations().unique().sort().each{println it.join()}}

Answer 22

Ruby, 51 bytes

->s{puts s.chars.permutation.map(&:join).uniq.sort}

Answer 23

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.

Answer 24

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.

Answer 25

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

Answer 26

Japt v2.0a0 -R, 5 bytes

á â n

Try it

Answer 27

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!

Answer 28

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!

Answer 29

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