11
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ Strongly related, possible dupe \$\endgroup\$ – Giuseppe Jun 17 at 18:02
  • 4
    \$\begingroup\$ @Giuseppe I don't think this is a dupe of that; the specifics of this question allow for much shorter implementations \$\endgroup\$ – ArBo Jun 17 at 18:11
  • 4
    \$\begingroup\$ Adding some testcases may help. \$\endgroup\$ – tsh Jun 18 at 3:45
  • 1
    \$\begingroup\$ @JonathanAllan Good suggestion! Title changed accordingly. \$\endgroup\$ – I_P_Edwards Jun 18 at 17:38

29 Answers 29

29
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ itertools is very verbose in its function names \$\endgroup\$ – qwr Jun 18 at 17:30
16
\$\begingroup\$

05AB1E, 3 bytes

œÙg

Try it online!

Explanation

  g  # length of the list
 Ù   # of unique
œ    # permutations
     # of the input
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Looks like "lel", +1! :D \$\endgroup\$ – KeyWeeUsr Jun 18 at 9:12
5
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ function(s,!=factorial)(!nchar(s))/prod(!table(strsplit(s,""))) will work. the el( ) is reduntant - table knows to look for the elements.... \$\endgroup\$ – Zahiro Mor Jun 18 at 7:52
  • 1
    \$\begingroup\$ @ZahiroMor ah, of course. I had intended to test that but never got around to it. \$\endgroup\$ – Giuseppe Jun 18 at 13:29
4
\$\begingroup\$

APL (Dyalog Unicode), 14 bytes

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

Try it online!

Returns the result as a singleton.

\$\endgroup\$
  • \$\begingroup\$ -> to make it return simple scalars, ÷⍨/g⌸,g←!⊢∘≢ for -2 \$\endgroup\$ – ngn Aug 4 at 12:56
4
\$\begingroup\$

Japt, 5 3 bytes

-2 bytes thanks to @Shaggy

á l

Try it online!

\$\endgroup\$
  • \$\begingroup\$ TIO seems to be running an old version of Japt, allowing you to ditch the â. \$\endgroup\$ – Shaggy Jun 17 at 20:38
  • \$\begingroup\$ @Shaggy Lol, I did not noticed that. thanks! \$\endgroup\$ – Luis felipe De jesus Munoz Jun 18 at 12:10
4
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ (Potential floating-point rounding error; use t=t* if you want to avoid that.) \$\endgroup\$ – Neil Jun 18 at 9:21
  • \$\begingroup\$ @Neil Yeah it failed when the input is aaadegfbbbccc exactly due to the floating-point rounding error \$\endgroup\$ – Shieru Asakoto Jun 18 at 10:01
  • \$\begingroup\$ Huh, how did you find that test case? \$\endgroup\$ – Neil Jun 18 at 10:09
  • \$\begingroup\$ @Neil Keep adding characters to the string until such rounding error occurs lol \$\endgroup\$ – Shieru Asakoto Jun 18 at 14:52
  • \$\begingroup\$ @ShieruAsakoto Title has been changed; count is much better. Thanks, and nice answer! \$\endgroup\$ – I_P_Edwards Jun 18 at 17:40
4
\$\begingroup\$

J, 15, 14 bytes

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

Try it online!

-1 byte thanks to FrownyFrog

\$\endgroup\$
  • \$\begingroup\$ ~. can be = \$\endgroup\$ – FrownyFrog Aug 4 at 9:36
  • \$\begingroup\$ Nice. Thank you, @FrownyFrog \$\endgroup\$ – Jonah Aug 4 at 15:08
3
\$\begingroup\$

Jelly, 4 bytes

Œ!QL

Try it online!

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

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

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.

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

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.

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

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!

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

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
\$\endgroup\$
2
\$\begingroup\$

Ruby, 41 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think you need to_a \$\endgroup\$ – ArBo Jun 18 at 8:04
  • 1
    \$\begingroup\$ And anonymous functions/lambdas are acceptable, so you can remove the f= part. (In TIO move it to Header to not get counted.) \$\endgroup\$ – manatwork Jun 18 at 8:05
2
\$\begingroup\$

Perl 5, 43 bytes

Uses the method in @ArBo's Python answer.

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

Try it online!

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

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

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

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 (#)
\$\endgroup\$
  • \$\begingroup\$ Is prm an ok specific operator? I don't think vanilla k has it? \$\endgroup\$ – Henry Henrinson Jun 18 at 22:28
  • \$\begingroup\$ Yup - only exists in oK per the manual \$\endgroup\$ – streetster Jun 19 at 9:31
  • \$\begingroup\$ @HenryHenrinson afaik it's not in k4. in early k5 it was !-n. in late k5 and k6 it became prm. k7(shakti) has prm too. \$\endgroup\$ – ngn Jun 20 at 17:18
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Okay, I could golf a byte by making it iterative instead of recursive: s->{int r=1,i=s.length();for(;i>0;)r=r*i/~-s.substring(--i).split(s.charAt(i)+"",-1).length;return r;}. \$\endgroup\$ – Olivier Grégoire Jun 20 at 12:29
  • \$\begingroup\$ @OlivierGrégoire Thanks! Btw, do you see something to make the second approach (generating all unique permutations in a set) shorter? I have the feeling some bytes can be saved, but tried some things and most were slightly longer instead of shorter.. But it still looks overly long tbh. \$\endgroup\$ – Kevin Cruijssen Jun 20 at 12:49
  • \$\begingroup\$ I've been working on it, trying to use streams and count, like this: s->{long r=1,i=s.length();for(;i>0;)r=r*i/(s.chars().skip(--i).filter(c -> c==s.charAt(i)).count()+1);return r;} but without success so far... \$\endgroup\$ – Olivier Grégoire Jun 20 at 13:00
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I thought unique returned unique rows already? Or is that only for tables? \$\endgroup\$ – Giuseppe Jun 17 at 17:59
  • \$\begingroup\$ @Giuseppe For numeric/char 2D arrays unique would linearize first. For tables I think you are right; I didn't know that! \$\endgroup\$ – Luis Mendo Jun 17 at 18:00
  • 1
    \$\begingroup\$ Ah, I know where I got the idea -- unique in MATLAB does take rows for tables; R's unique takes unique rows of matrices or data frames. Too many array languages with the same commands that do slightly different things... \$\endgroup\$ – Giuseppe Jun 17 at 21:33
1
\$\begingroup\$

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.

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

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to the site! Doesn't really matter since it is invalid but could you make your invalid answer more accurate by using 999999 instead of 100000? \$\endgroup\$ – Wheat Wizard Jun 18 at 23:40
  • \$\begingroup\$ Yup, good idea, thanks. \$\endgroup\$ – Henry Henrinson Jun 19 at 0:31
  • 1
    \$\begingroup\$ And maybe edit the explanation to reflect that change too? \$\endgroup\$ – Selcuk Jun 19 at 23:03
1
\$\begingroup\$

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.

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

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!

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

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

\$\endgroup\$
  • \$\begingroup\$ { deduplicates a list for a byte less than .{. \$\endgroup\$ – hakr14 Aug 4 at 15:17
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ #(%*/)&:!#/.~ should save another byte \$\endgroup\$ – miles Aug 7 at 22:52
1
\$\begingroup\$

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!

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

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
\$\endgroup\$
0
\$\begingroup\$

Stax, 3 bytes

═1╪

Run and debug it

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