Pascal's rule 집합의 하위 집합을 계산할 때 훌륭한 집합이 포함됩니다.고유하지 않은 세트에 대한 파스칼의 정리?
세트에 중복 항목이 포함되어있는 경우이 규칙이 수정 되었습니까?
예를 들어 문자 A, B, C, D의 조합 수를 찾으려고하면 1 + 4 + 6 + 4 + 1 (파스칼의 삼각형에서 나온 것) = 16 , 또는 "편지 없음 사용"항목을 제거하면 15입니다.
문자 세트가 A, B, B, B, C, C, D이면 어떻게 될까요? 손으로 계산하면, 부분 집합의 합이 1 + 4 + 8 + 11 + 11 + 8 + 4 + 1 = 48이라고 결정할 수 있습니다. 그러나 이것은 내가 아는 삼각형과 일치하지 않습니다.
질문 : 세트의 복제 엔티티를 고려하여 파스칼의 삼각형을 어떻게 수정합니까?
얼마나 많은 서브 멀티 세트가 3 개의 요소를 갖고 있는지 알고 싶습니다. 이것에 대한 수학은 매우 까다로워집니다. 아이디어는 거기에 도달하는 모든 방법의 조합을 함께 추가하고자하는 것입니다. C (3,4) = 중복 요소가없는 4 가지 방법이 있습니다. B는 C (1,3) = 3 방법으로 두 번 반복 될 수 있습니다. B는 한 번에 3 번 반복 할 수 있습니다. 그리고 C는 C (1,3) = 3 방법으로 두 번 반복 될 수 있습니다. 총 11 가지. (손에 들고있는 당신 10 명은 틀렸어. 미안.)
일반적으로 그 논리를 시도하는 것은 너무 어렵습니다. 그것을 추적하는 더 쉬운 방법은 계수에 원하는 항이있는 다항식을 작성하는 것입니다. 파스칼의 삼각형에 대해서 이것은 쉽다. 다항식은 (1 + x)^n이다. 반복 사각형을 사용하여보다 효율적으로 계산할 수 있습니다. 요소가 두 번 반복되는 경우 (1 + x + x^2) 요소가 있습니다. 3 번은 (1 + x + x^2 + x^3)이됩니다.당신이 코드에서이 번호를 생성하려는 경우, 당신의 생각과 코드를 구성 할 다항식 트릭을 사용
(1 + x) (1 + x + x^2 + x^3) (1 + x + x^2) (1 + x)
= (1 + 2x + 2x^2 + 2x^3 + x^4)(1 + 2x + 2x^2 + x^3)
= 1 + 2x + 2x^2 + x^3 +
2x + 4x^2 + 4x^3 + 2x^4 +
2x^2 + 4x^3 + 4x^4 + 2x^5 +
2x^3 + 4x^4 + 4x^5 + 2x^6 +
x^4 + 2x^5 + 2x^6 + x^7
= 1 + 4x + 8x^2 + 11x^3 + 11x^4 + 8x^5 + 4x^6 + x^7
다음과 같이 그래서 특정 문제가 해결 될 것이다. (당신은 계수의 배열로 작업 할 것입니다.)
세트에는 고유 항목 만 있습니다. 중복이 있으면 더 이상 세트가 아닙니다.
수학 세트에 고유 항목이 포함되어 있어도 프로그래밍의 실제 세계에서 '세트'에 중복 항목 문제가 발생할 수 있습니다. 예제는 Lisp 유니온의 this thread을 참조하십시오.
파스칼의 삼각형을 전혀 수정할 필요가 없습니다. C (k, n)을 공부하면 알 수 있습니다. 원래 결과를 동등한 문자의 순열을 고려하여 나누어야합니다.
예 : A B1 B2 C1 D1 == A B2 B1 C1 D1 따라서 C (5,5)를 C (2,2)로 나누어야합니다.
서브 멀티 세트의 총 수를 원하면 도움이됩니다. 예를 들어 5 개의 요소를 가진 서브 멀티 세트의 총 수를 풀고 싶다면 도움이되지 않습니다. – user11318
C (5,5) = 1, C (2,2)처럼 ... 이것은 내가 필요한 것에 가깝지 않습니다. – billjamesdev
중복되지 않은 경우 (이전 포스터에서 설명한대로) 각 요소는 부분 집합 안팎에 있습니다. 따라서 2^n 개의 하위 집합이 있습니다. 중복으로 ("다중 세트"에서) 각 요소가 "하위 다중 세트"에있는 횟수를 고려해야합니다. m_1, m_2 ... m_n이 각 요소가 반복되는 횟수를 나타내면 하위 가방 수는 (1 + m_1) * (1 + m_2) * ... (1 + m_n)이됩니다.
예, 세트를 고려하지 않으려면 '요인'을 고려하십시오. 몇 팩터가 되는가 :
p1^a1.p2^a2....pn^an
만약 p1이 뚜렷한 소수라면. ai가 모두 1이면 숫자는 2^n입니다. 일반적으로 대답은 David Nehme이 지적한 것처럼 (a1 + 1) (a2 + 1) ... (an + 1)입니다.
오, 그리고 당신의 답은 잘못되었습니다. 빈 세트를 계산하고 싶지 않으면 48이나 47이어야합니다.
일반적으로 다중 세트 또는 백이라고합니다. – Hank
나는 용어에 대한 말다툼이 가장 대중적인 반응이라고 우울하게 생각한다. 누군가 질문 한 질문을 실제로 이해하지 못 했습니까? – user11318
수학은 매우 정확한 정의에 따라 작성되므로 "용어"는 중요합니다. 임의로 집합의 정의를 변경하면 집합에 정의 된 연산이 의미를 변경하거나 의미가 없어 질 수 있습니다. – Dima