Count All Possible Unique Combinations of Letters in a Word

Question

You are given a string, which will contain ordinary a-z characters. (You can assume this will always be the case in any test, and assume that all letters will be lowercase as well). You must determine how many unique combinations can be made of the individual characters in the string, and print that number.

However, duplicate letters can be ignored in counting the possible combinations. In other words, if the string given is "hello", then simply switching the positions of the two ls does not count as a unique phrase, and therefore cannot be counted towards the total.

Shortest byte count wins, looking forward to seeing some creative solutions in non-golfing languages!

Examples:

hello -> 60
aaaaa -> 1
abcde -> 120

Answer 1

Python 2, 50 48 bytes

f=lambda s:s==''or len(s)*f(s[1:])/s.count(s[0])

Try it online!

No boring built-ins! To my surprise, this is even shorter than the brute force approach, calculating all of the permutations with itertools and taking the length.

This function uses the formula

\$\text{# of unique permutations} = \frac{\text{(# of elements)!}}{\prod_{\text{unique elements}}{\text{(# of occurences of that element)!}}}\$

and computes it on the fly. The factorial in the numerator is calculated by multiplying by len(s) in each function call. The denominator is a bit more subtle; in each call, we divide by the number of occurences of that element in what's left of the string, ensuring that for every character c, all numbers between 1 and the amount of occurences of c (inclusive) will be divided by exactly once. Since we divide only at the very end, we're guaranteed not to have any problems with Python 2's default floor division.

Answer 2

05AB1E, 3 bytes

œÙg

Try it online!

Explanation

  g  # length of the list
 Ù   # of unique
œ    # permutations
     # of the input

Answer 3

CJam, 4 bytes

le!,

Try it online!

Explanation

Read line as a string (l), unique permutations as an array of strings (e!), length (,), implicit display.

Answer 4

R, 69 65 bytes

function(s,`!`=factorial)(!nchar(s))/prod(!table(strsplit(s,"")))

Try it online!

4 bytes saved thanks to Zahiro Mor in both answers.

Computes the multinomial coefficient directly.

R, 72 68 bytes

function(s,x=table(strsplit(s,"")))dmultinom(x,,!!x)*sum(1|x)^sum(x)

Try it online!

Uses the multinomial distribution function provided by dmultinom to extract the multinomial coefficient.

Note that the usual (golfier) x<-table(strsplit(s,"")) doesn't work inside the dmultinom call for an unknown reason.

Answer 5

JavaScript (Node.js), 49 bytes

t=t* is used instead of t*= to avoid rounding error (the |t rounds down the number) as t=t* guarantees that all intermediate (operator-wise) results are whole numbers.

a=>[...a].map(g=x=>t=t*y++/(g[x]=-~g[x]),t=y=1)|t

Try it online!

a=>
 [...a].map(        // Loop over the characters
  g=x=>
   t=t*             // using t*= instead may result in rounding error 
    y++             // (Length of string)!
    /(g[x]=-~g[x])  // divided by product of (Count of character)!
  ,t=y=1            // Initialization
 )
 |t

Answer 6

APL (Dyalog Unicode), 14 bytes

!∘⍴÷⊂×.(!∘⍴∩)∪

Try it online!

Returns the result as a singleton.

Answer 7

Japt, 5 3 bytes

-2 bytes thanks to @Shaggy

á l

Try it online!

Answer 8

J, 15, 14 bytes

[:#@=i.@!@#A.]

Try it online!

-1 byte thanks to FrownyFrog

Answer 9

Jelly, 4 bytes

Œ!QL

Try it online!

Simply does what was asked: find permutations of input, uniquify and print the length.

Answer 10

C# (Visual C# Interactive Compiler), 59 bytes

f=s=>s==""?1:s.Length*f(s.Substring(1))/s.Count(c=>c==s[0])

Port of @ArBo's Python 2 answer.

Try it online.

Answer 11

Brachylog, 3 bytes

pᶜ¹

Try it online!

       The output is
 ᶜ¹    the number of unique
p      permutations of
       the input.

pᵘl does pretty much exactly the same thing.

Answer 12

Python 2, 57 bytes

lambda s:len(set(permutations(s)))
from itertools import*

Try it online!

Self-documenting: Return the length of the set of unique permutations of the input string.

Python 3, 55 bytes

Credit goes to ArBo on this one:

lambda s:len({*permutations(s)})
from itertools import*

Try it online!

Answer 13

APL (Dyalog Unicode), 24 bytes

⎕CY'dfns'
{≢∪↓⍵[pmat≢⍵]}

Try it online!

Simple Dfn, takes a string as argument.

How:

⎕CY'dfns'      ⍝ Copies the 'dfns' namespace.
{≢∪↓⍵[pmat≢⍵]} ⍝ Main function
          ≢⍵   ⍝ Number of elements in the argument (⍵)
      pmat     ⍝ Permutation Matrix of the range [1..≢⍵]
    ⍵[      ]  ⍝ Index the argument with that matrix, which generates all permutations of ⍵
   ↓           ⍝ Convert the matrix into a vector of strings
  ∪            ⍝ Keep only the unique elements
 ≢             ⍝ Tally the number of elements

Answer 14

Ruby, 41 bytes

f=->s{s.chars.permutation.to_a.uniq.size}

Try it online!

Answer 15

Perl 5, 43 bytes

Uses the method in @ArBo's Python answer.

sub c{!@_||@_*c(@_[1..$#_])/grep/$_[0]/,@_}

Try it online!

Answer 16

Perl 6, 33 30 chars (34 31 bytes)

Fairly straight forward Whatever block. comb splits the string into letters, permutations gets all possible combinations. Because of the way coercion to Set need be joined first ( » applies join to each element in the list).

+*.comb.permutations».join.Set

Try it online!

(previous answer used .unique but Sets guarantee uniqueness, and numerify the same, so it saves 3).

Answer 17

K (oK), 12 bytes

Solution:

#?x@prm@!#x:

Try it online!

Explanation:

Uses the oK built-in prm:

{[x]{[x]$[x;,/x ,''o'x ^/:x;,x]}@$[-8>@x;!x;x]}

... which, due to x^/:x basically generates the permutations of "helo" not "hello", hence we need to generate the permutations of 0 1 2 3 4, use them to index into "hello" and then take the count of the unique.

#?x@prm@!#x: / the solution
          x: / store input as x
         #   / count (#) length
        !    / range (!) 0..n
    prm@     / apply (@) to function prm
  x@         / apply permutations to input x
 ?           / take the distinct (?)
#            / count (#)

Answer 18

Java 8, 103 102 bytes

s->{int r=1,i=s.length();for(;i>0;)r=r*i/~-s.substring(--i).split(s.charAt(i)+"",-1).length;return r;}

Port of @ArBo's Python 2 answer.
-1 byte thanks to @OlivierGrégoire by making it iterative instead of recursive.

Try it online.

Actually generating all unique permutations in a Set and getting its size would be 221 bytes:

import java.util.*;s->{Set S=new HashSet();p(s,S,0,s.length()-1);return S.size();}void p(String s,Set S,int l,int r){for(int i=l;i<=r;p(s.replaceAll("(.{"+l+"})(.)(.{"+(i++-l)+"})(.)(.*)","$1$4$3$2$5"),S,l+1,r))S.add(s);}

Try it online.

Answer 19

MATL, 9 bytes

jY@XuZy1)

Try it online!

Explanation:

j input as string
Y@ get permutations
Xu unique members
Zy size matrix
1) first member of size matrix

Answer 20

Octave / MATLAB, 35 bytes

@(s)size(unique(perms(s),'rows'),1)

Anonymous function that takes a character vector and produces a number.

In MATLAB this can be shortened to size(unique(perms(s),'ro'),1) (33 bytes).

Try it online!

Explanation

@(s)                                  % Anonymous function with input s
                perms(s)              % Permutations. Gives a char matrix
         unique(        ,'rows')      % Deduplicate rows
    size(                       ,1)   % Number of rows

Answer 21

Retina 0.8.2, 73 bytes

(.)(?=(.*?\1)*)
/1$#2$*1x1$.'$*
^
1
+`1(?=1*/(1+)x(\1)+$)|/1+x1+$
$#2$*
1

Try it online! Uses @ArBo's formula, but evaluates from right-to-left as this can be done in integer arithmetic while still minimising the size of the unary values involved. Explanation:

(.)(?=(.*?\1)*)
/1$#2$*1x1$.'$*

For each character, count how many remaining duplicates there are and how many further characters there are, add one to each to take the current character into account, and separate the values so we know which ones are to be divided and which are to be multiplied.

^
1

Prefix a 1 to produce a complete expression.

+`1(?=1*/(1+)x(\1)+$)|/1+x1+$
$#2$*

Repeatedly multiply the last and third last numbers while dividing by the second last number. This replaces the last three numbers.

1

Convert to decimal.

Answer 22

K, 27 bytes

*/[1+!#:x]%*/{*/1+!x}'#:'x:

K, 16 bytes - not a real answer

#?(999999#0N)?\:

Take 999999 random permutations of the input string, take the unique set of them and count the length. Most of the time it will give the right answer, for shortish strings.

Improved thanks to @Sriotchilism O'Zaic, @Selcuk

Answer 23

Wolfram Language (Mathematica), 32 bytes

Characters/*Permutations/*Length

Try it online!

Explanation: Right-composition with /* applies these three operators one after the other to the function argument, from left to right:

• Characters converts the input string to a list of characters.

• Permutations makes a list of all unique permutations of this character list.

• Length returns the length of this list of unique permutations.

This method is very wasteful for long strings: the unique permutations are actually listed and counted, instead of using a Multinomial to compute their number without listing.

Answer 24

F# (Mono), 105 bytes

let rec f s=if s=""then 1 else s.Length*(f(s.Substring 1))/(s|>Seq.sumBy(fun c->if c=s.[0]then 1 else 0))

Try it online!

Answer 25

Pyth, 5 4 bytes

l{.p

Try it online!

This assumes the input is a python string literal. If input must be raw text, this 5-byte version will work:

l{.pz

Either way, it just computes all permutations of the input as a list, deduplicates it and gets the number of elements in it, and implicitly prints that number.

-1 byte thanks to @hakr14

Answer 26

J, 14 13 bytes

#(%*/)&:!#/.~

Try it online!

1 byte thanks to miles

#                  length
         #/.~      counts of each unique character
 (%*/)             divide left by the product of right
      &:!          after applying ! to both

Answer 27

PHP, 77 bytes

function f($s){return!$s?:strlen($s)*f(substr($s,1))/substr_count($s,$s[0]);}

Try it online!

This is basically just a PHP port of @ArBo's winning Python answer which is ridiculously more clever than the recursive answer I originally had. Bravo!

Answer 28

Ohm v2, 4 bytes

ψD∩l

Try it online!

Explanation

   l    output the lenght of
  ∩     the set intersection between
ψD      two copies of all possible permutation of input

Answer 29

Stax, 3 bytes

═1╪

Run and debug it