12
\$\begingroup\$

Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are n integers, and each group of indistinguishable numbers has length n_i, this is n! / (n_1! * n_2! * ...)

Rules

  • Input will be some form of list as arguments to a function or the program with 1 to 12 non-negative integers.

  • Output will be printing or returning the number of permutations as described above.

  • No standard loopholes or built-in functions (generating permutations, combinations, etc.). Factorials are allowed.

Test Cases

Inputs:

1, 3000, 2, 2, 8
1, 1, 1
2, 4, 3, 2, 3, 4, 4, 4, 4, 4, 1, 1

Outputs:

60
1
83160
\$\endgroup\$
  • \$\begingroup\$ when you say no builtins, does this include what I did when I used a builtin for generating all the permutations? \$\endgroup\$ – Maltysen Apr 24 '16 at 20:45
  • 1
    \$\begingroup\$ This looks largely the same as Compute the multinomial coefficient. Does counting identical entries for the input make it sufficiently different not to be a dupe? \$\endgroup\$ – xnor Apr 24 '16 at 20:47
  • \$\begingroup\$ @xnor well here you actually have to count the duplicates, so it's not as straightforward I suppose. The other is pretty much straight plugging in values. \$\endgroup\$ – qwr Apr 24 '16 at 20:50
  • \$\begingroup\$ @Maltysen sadly yes, I will have to update the question \$\endgroup\$ – qwr Apr 24 '16 at 20:50
  • 1
    \$\begingroup\$ @LuisMendo Yes it is, though it should not make a difference as far as I can imagine \$\endgroup\$ – qwr Apr 24 '16 at 21:11

10 Answers 10

6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Why don't you put /l.count(l[0]) at the end? Then you don't need that icky floating point. \$\endgroup\$ – feersum Apr 24 '16 at 22:29
4
\$\begingroup\$

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

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

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

JavaScript (ES6), 64 61 bytes

a=>a.sort().map((x,i)=>r=r*++i/(x-y?(y=x,c=1):++c),y=r=-1)|-r

Uses the formula given, except calculating each factorial incrementally (so for example the r=r*++i effectively calcluates n!).

Edit: Originally I accepted any finite numbers but I saved 3 bytes when @user81655 pointed out that I only needed to support positive integers (although I actually accept non-negative integers).

\$\endgroup\$
  • \$\begingroup\$ r*=++i/(x-y?(y=x,c=1):++c),y=r=-1)|-r? \$\endgroup\$ – user81655 Apr 25 '16 at 4:39
  • \$\begingroup\$ @user81655 Ah, I hadn't read the question thoroughly enough and overlooked that I could rely on the values being positive integers. I don't like the *= though as that introduces rounding errors. \$\endgroup\$ – Neil Apr 25 '16 at 7:37
2
\$\begingroup\$

Pyth, 11 bytes

/.!lQ*F/V._

Test suite

Uses the standard formula, n! / (count1! * count2! * ...), except that the factorials of the counts are found by counting how many times each element occurs in the prefix leading up to that, then multiplying all such numbers together.

Explanation:

/.!lQ*F/V._
/.!lQ*F/V._QQ    Implicit variable introduction.
                 Q = eval(input())
         ._Q     Form all prefixes of the input.
       /V   Q    Count how many times each element occurs in the prefix
                 ending with that element.
     *F          Fold on multiplication - take the product.
 .!lQ            Take the factorial of the input length
/                Divide.
\$\endgroup\$
1
\$\begingroup\$

Pyth - 14 12 bytes

/F.!M+lQ/LQ{

Test Suite.

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

Ruby, 75 74 bytes

Kinda wish that Ruby's Math module had a factorial function so I didn't have to build my own.

->l{f=->x{x<2?1:x*f[x-1]};l.uniq.map{|e|f[l.count e]}.inject f[l.size],:/}
\$\endgroup\$
1
\$\begingroup\$

CJam, 17 bytes

q~_,\$e`0f=+:m!:/

Test it here.

Explanation

q~   e# Read input and evaluate.
_,   e# Duplicate and get length.
\$   e# Swap with other copy and sort it.
e`   e# Run-length encode. Since the list is sorted, this tallies the numbers.
0f=  e# Select the tally of each number.
+    e# Prepend the length of the input.
:m!  e# Compute the factorial of each number in the list.
:/   e# Fold division over it, which divides each factorial of a tally into
     e# the factorial of the length.
\$\endgroup\$
1
\$\begingroup\$

Jelly, 8 bytes

W;ĠL€!:/

Try it online!

W;ĠL€!:/ example input:             [1, 3000, 2, 2, 8]
W        wrap:                      [[1, 3000, 2, 2, 8]]
  Ġ      group index by appearance: [[1], [3, 4], [5], [2]]
 ;       concatenate:               [[1, 3000, 2, 2, 8], [1], [3, 4], [5], [2]]
   L€    map by length:             [5, 1, 2, 1, 1]
     !   [map by] factorial:        [120, 1, 2, 1, 1]
      :/ reduce by division:        120÷1÷2÷1÷1 = 60
\$\endgroup\$
1
\$\begingroup\$

J, 13 bytes

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

Usage

   f =: #(%*/)&:!#/.~
   f 1 3000 2 2 8
60
   f 1 1 1
1
   f 2 4 3 2 3 4 4 4 4 4 1 1
83160

Explanation

#(%*/)&:!#/.~  Input: A
         #/.~  Partition A by equal values and get the size of each, these are the tallies
#              Get the size of A
      &:!      Take the factorial of both the size and the tallies
   */          Reduce using multiplication the factorial of the tallies
  %            Divide the factorial of the size by that product and return
\$\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.