Permutaciones con elementos indistinguibles

12

Dada una lista de enteros, genera el número de permutaciones de los enteros, con permutaciones indistinguibles contadas una vez. Si hay nnúmeros enteros, y cada grupo de números indistinguibles tiene longitud n_i, esto esn! / (n_1! * n_2! * ...)

Reglas

  • La entrada será alguna forma de lista como argumentos para una función o el programa con 1 a 12 enteros no negativos.

  • La salida imprimirá o devolverá el número de permutaciones como se describió anteriormente.

  • No hay lagunas estándar ni funciones integradas (que generan permutaciones, combinaciones, etc.). Se permiten los factoriales.

Casos de prueba

Entradas:

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

Salidas:

60
1
83160
qwr
fuente
cuando dices no incorporados, ¿incluye esto lo que hice cuando usé un incorporado para generar todas las permutaciones?
Maltysen
1
Esto se ve en gran medida igual que Calcular el coeficiente multinomial . ¿Contar entradas idénticas para la entrada hace que sea lo suficientemente diferente como para no ser un engañado?
xnor
@xnor bueno, aquí tienes que contar los duplicados, así que no es tan sencillo, supongo. El otro es prácticamente directo conectando valores.
qwr
@Maltysen lamentablemente sí, tendré que actualizar la pregunta
qwr
1
@LuisMendo Sí lo es, aunque no debería hacer una diferencia por lo que puedo imaginar
qwr

Respuestas:

6

Python, 48 bytes

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

Una implementación recursiva.

En la fórmula, n! / (n_1! * n_2! * ...)si eliminamos el primer elemento (digamos que es 1), el número de permutación para los n-1elementos restantes es

(n-1)! / ((n_1-1)! * n_2! * ...) ==
n! / n / (n_1! / n_1! * n_2! * ...) == 
n/n_1 * (n! / (n_1! * n_2! * ...)`)

Entonces, obtenemos la respuesta multiplicando por n/n1, la fracción recíproca de elementos que iguala al primero, por el resultado recursivo para el resto de la lista. La lista vacía da el caso base de 1.

xnor
fuente
¿Por qué no lo pones /l.count(l[0])al final? Entonces no necesitas ese punto flotante asqueroso.
feersum
4

MATL , 14 13 12 bytes

fpGu"@G=s:p/

Pruébalo en línea!

Explicación

El enfoque es muy similar al de la respuesta de @ Adnan .

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
Luis Mendo
fuente
3

05AB1E , 15 14 13 bytes

Código:

D©g!rÙv®yQO!/

Explicación:

               # 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

Utiliza la codificación CP-1252 .

Pruébalo en línea! .

Adnan
fuente
2

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

Utiliza la fórmula dada, excepto que calcula cada factorial de forma incremental (por ejemplo, el r=r*++icálculo efectivo n!).

Editar: Originalmente acepté cualquier número finito, pero ahorré 3 bytes cuando @ user81655 señaló que solo necesitaba admitir enteros positivos (aunque en realidad acepto enteros no negativos).

Neil
fuente
r*=++i/(x-y?(y=x,c=1):++c),y=r=-1)|-r?
user81655
@ user81655 Ah, no había leído la pregunta lo suficiente y pasé por alto que podía confiar en que los valores fueran enteros positivos. Sin *=embargo, no me gusta porque introduce errores de redondeo.
Neil
2

Pyth, 11 bytes

/.!lQ*F/V._

Banco de pruebas

Utiliza la fórmula estándar n! / (count1! * count2! * ...), excepto que los factores de los recuentos se encuentran contando cuántas veces se produce cada elemento en el prefijo que conduce a eso, y luego multiplicando todos esos números.

Explicación:

/.!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.
isaacg
fuente
1

Ruby, 75 74 bytes

Desearía que el Mathmódulo de Ruby tuviera una función factorial para que no tuviera que construir la mía.

->l{f=->x{x<2?1:x*f[x-1]};l.uniq.map{|e|f[l.count e]}.inject f[l.size],:/}
Tinta de valor
fuente
1

CJam, 17 bytes

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

Pruébalo aquí.

Explicación

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.
Martin Ender
fuente
1

Jalea, 8 bytes

W;ĠL€!:/

Pruébalo en línea!

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
Monja permeable
fuente
1

J, 13 bytes

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

Uso

   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

Explicación

#(%*/)&:!#/.~  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
millas
fuente