주어진 숫자 'n'에 합쳐진 'p'숫자의 순열 수 찾기

Question

동적 프로그래밍 문제를 해결하기 위해 노력 중이며 수의 'p'숫자 순열 'n'까지 합계합니다. p 숫자 세트의 각 숫자는 0에서 n까지이어야합니다.

예를 들어, N = 4, p = 3, I는 I이 DP 접근 시작 12 순열

{4,0,0},{0,4,0},{0,0,4} 
{2,2,0},{2,0,2},{0,2,2} 
{1,3,0},{1,0,3},{0,1,3} 
{1,1,2},{1,2,1},{2,1,1} 

다음의 경우.

n(i,j) represents number of ways of representing n using i,j in p positions 

내 기본 케이스는 p = 3 명에 대한 예를 들면

n(i,0) = n(0,i) = p 

(N (4,0) 될 것은 3 {4,0,0}, {0,4이며 0}, 0,0,4}

재귀 경우

n(i,j) = n(i,j-1)*n(i-1,j) 

(예 : N (1,2) = N (1,1) * N까지의 재귀 N (0,2) (1,0) * n (0,1) * 2)

위의 방법으로 올바른 방향으로 진행하고 있는지 정확한지 알 수 없습니다. 저를 올바른 방향으로 인도하십시오.

Answer 1

내 의견과는 달리, 세트의 수와 순열 수를 동시에 계산하면이 문제는 실제로 해결하기가 더 쉽습니다.

각 집합을 실제로 생성하는 대신 카운트 만 필요한 경우 몇 가지 간단한 조합으로 직접 설정할 수 있습니다. 의 우리의 예를 들어 p = 3, n = 5를 해결하고 우리가 n = 5 공을 가정 해 봅시다 :

o o o o o 

이제 문제는 동일합니다, 몇 가지 할 수있는 우리 분할 각 그룹 [0, 5] 공을 가질 수 3의 그룹으로 공? 우리가 p - 1 = 2 막대기를 가지고 있다고 상상해보십시오. 5 개의 공, 5 개의 공, 2 개의 공 사이에 개별적으로 배치 할 수 있습니다. 예를 들면 다음과 같습니다.

| o o | o o o => (0, 2, 3) 
o | | o o o o => (1, 0, 4) 
o o o o | | o => (4, 0, 1) 

질문에 대한 답은 어떻게됩니까? 어쨌든 우리는 그 지팡이를 넣을 수 있고, n 구슬을 p 세트로 나눌 수 있습니다. 우리는 단지 p - 1 스틱을 가지고 p 숫자를 생성 할 필요가 있음을 주목하십시오 (첫번째 스틱 이전의 모든 볼이 첫 번째 그룹이고, 마지막 스틱 이후의 모든 볼이 마지막 그룹이며 두 스틱 사이의 모든 볼이 다른 그룹입니다).

이제 우리의 질문은 내 n 볼과 p - 1 막대기를 몇 가지 방법으로 정렬 할 수 있습니까? 당신은 n + (p - 1) 슬롯을 가진다고 생각할 수 있습니다. 그리고 당신은 공을위한 n 스팟을 골라 내고 있습니다. 나머지는 막대기가있는 곳입니다. 그래서에서

(n + (p - 1)) Choose n = (n + (p - 1))!/n!/(p - 1)! 

: 그것을 우리가 조합론의 기본 공식을 적용 할 수있는이 방법을 생각 (이것은 내가 심지어 증거를 확실히 본 적이없는 공리 합 규칙 및 제품의 규칙을 ... 사용하여 입증) 우리의 예는 7!/5!/2! = 21입니다.그리고 예제에서 보면 6!/4!/2! = 15이 될 것입니다. 몇 가지 순열을 놓쳤습니다 (예 : {0, 3, 1}).

간단한 재귀 방정식으로 DP로이를 풀 수도 있습니다. 기본적으로

`f(n, p) = Sum over i = 0 to n, f(n - i, p - 1)` 

일부 값을 메모하고 f을 메모하십시오. 첫 번째 구성원의 값을 S으로 선택한 다음 다음 재귀 호출이 다음 구성원 인 S을 선택한다는 식의 개념입니다. 기본 케이스는 아마도 f(0, p) = 1과 f(n, 0) = 0과 같을 것입니다. 그렇지 않으면 재귀 케이스를 사용할 수 있습니다. 닫힌 폼은 실제로 세트 자체가 필요하지 않더라도 분명히 훨씬 더 효과적입니다.