정수 목록이 주어지면 구별 할 수없는 순열이 한 번 계산 된 정수의 순열 수를 출력합니다. 이 경우 n
정수와 구별 숫자의 각 그룹이 길이 n_i
,이입니다n! / (n_1! * n_2! * ...)
규칙
-
입력은 1에서 12가 아닌 음수가 아닌 정수를 가진 함수 또는 프로그램에 대한 인수로 목록의 형식입니다.
-
출력은 위에서 설명한대로 순열 수를 인쇄하거나 반환합니다.
-
표준 허점이나 내장 함수가 없습니다 (순열, 조합 등 생성). 계승이 허용됩니다.
테스트 사례
입력 :
1, 3000, 2, 2, 8
1, 1, 1
2, 4, 3, 2, 3, 4, 4, 4, 4, 4, 1, 1
출력 :
60
1
83160
답변
파이썬, 48 바이트
f=lambda l:l==[]or len(l)*f(l[1:])/l.count(l[0])
재귀 적 구현.
수식 n! / (n_1! * n_2! * ...)
에서 첫 번째 요소 (예 1
:)를 제거하면 나머지 n-1
요소 의 순열 수 는
(n-1)! / ((n_1-1)! * n_2! * ...) ==
n! / n / (n_1! / n_1! * n_2! * ...) ==
n/n_1 * (n! / (n_1! * n_2! * ...)`)
따라서 우리 n/n1
는 첫 번째 요소와 동일한 요소의 역수 에을 곱하고 나머지 목록에 대한 재귀 결과를 곱하여 답을 얻습니다 . 빈 목록은 기본 사례 1을 나타냅니다.
답변
MATL , 14 13 12 바이트
fpGu"@G=s:p/
설명
이 접근법은 @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
답변
05AB1E , 15 14 13 바이트
암호:
D©g!rÙv®yQO!/
설명:
# 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
CP-1252 인코딩을 사용합니다 .
답변
자바 스크립트 (ES6), 64 61 바이트
a=>a.sort().map((x,i)=>r=r*++i/(x-y?(y=x,c=1):++c),y=r=-1)|-r
각 계승을 점진적으로 계산하는 것을 제외하고 주어진 공식을 사용합니다 (예 : r=r*++i
효과적으로 계산 n!
).
편집 : 원래 유한 수를 허용했지만 @ user81655가 양의 정수만 지원해야한다고 지적했을 때 3 바이트를 절약했습니다 (실제로 음이 아닌 정수를 허용하지만).
답변
Pyth, 11 바이트
/.!lQ*F/V._
n! / (count1! * count2! * ...)
접두사에서 각 요소가 발생하는 횟수를 세고 해당 숫자를 모두 곱하여 카운트의 계승을 찾는 것을 제외하고 표준 수식을 사용합니다 .
설명:
/.!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.
답변
답변
루비, 75 74 바이트
Kinda는 Ruby의 Math
모듈이 계승 기능을 가지고 있기 때문에 내 자신을 만들 필요가 없었기를 바랍니다.
->l{f=->x{x<2?1:x*f[x-1]};l.uniq.map{|e|f[l.count e]}.inject f[l.size],:/}