Permutations with Indistinguishable Items
Python, 48 bytes
f=lambda l:l==[]or len(l)*f(l[1:])/l.count(l[0])
A recursive implementation.
In the formula, n! / (n_1! * n_2! * ...)
, if we remove the first element (say it's 1
), the number of permutation for the remaining n-1
elements is
(n-1)! / ((n_1-1)! * n_2! * ...) ==
n! / n / (n_1! / n_1! * n_2! * ...) ==
n/n_1 * (n! / (n_1! * n_2! * ...)`)
So, we get the answer by multiplying by n/n1
, the reciprocal-fraction of elements that equal the first one, by the recursive result for the rest of the list. The empty list gives the base case of 1.
MATL, 14 13 12 bytes
fpGu"@G=s:p/
Try it online!
Explanation
The approach is very similar to that in @Adnan's answer.
f % Take input implicitly. Push array of indices of nonzero entries.
% This gives [1 2 ... n] where n is input length.
p % Product (compute factorial)
Gu % Push input. Array of its unique elements
" % For each of those unique values
@ % Push unique value of current iteration
G=s % Number of times (s) it's present (=) in the input (G)
:p % Range, product (compute factorial)
/ % Divide
% End for each implicitly. Display implicitly
05AB1E, 15 14 13 bytes
Code:
D©g!rÙv®yQO!/
Explanation:
# implicit input
D© # duplicate and save a copy to register
g! # factorial of input length (total nr of permutations without duplicates)
rÙv # for each unique number in input
®yQO! # factorial of number of occurances in input
/ # divide total nr of permutations by this
# implicit output
Uses CP-1252 encoding.
Try it online!.