Find the $n$'th integer composition with a fixed number of components in lexicographical order

139 Views Asked by At

lets there is a number (N) and partitions (p), I have all the possible combinations, each combination sums to N. I want to calculate the nth term of these sequences/ combinations given N and p.

N = 7, p = 3

1: 1,1,5
2: 1,2,4
3: 1,3,3
4: 1,4,2
5: 1,5,1

6: 2,1,4
7: 2,2,3
8: 2,3,2
9: 2,4,1

10: 3,1,3
11: 3,2,2
12: 3,3,1

13: 4,1,2
14: 4,2,1

15: 5,1,1

N = 7, p = 4

1: 1,1,1,4
2: 1,1,2,3
3: 1,1,3,2
4: 1,1,4,1

5: 1,2,1,3
6: 1,2,2,2
7: 1,2,3,1

8: 1,3,1,2
9: 1,3,2,1

10: 1,4,1,1

11: 2,1,1,3
12: 2,1,2,2
13: 2,1,3,1

14: 2,2,1,2
15: 2,2,2,1

16: 2,3,1,1

17: 3,1,1,2
18: 3,1,2,1

19: 3,2,1,1

20: 4,1,1,1

N = 7, p = 5

1: 1,1,1,1,3
2: 1,1,1,2,2
3: 1,1,1,3,1

4: 1,1,2,1,2
5: 1,1,2,2,1

6: 1,1,3,1,1

7: 1,2,1,1,2
8: 1,2,1,2,1

9: 1,2,2,1,1

10: 1,3,1,1,1

11: 2,1,1,1,2
12: 2,1,1,2,1

13: 2,1,2,1,1

14: 2,2,1,1,1

15: 3,1,1,1,1
1

There are 1 best solutions below

9
On BEST ANSWER

The way you divided up your lists already speaks to a way of doing it. Let $a_1, \ldots, a_n$ denote the elements of the answer. The number of compositions starting with $k$ is $\binom{N-k-1}{p-2}$. So compute partial sums $$ s_m(N,p) = \sum_{k=1}^m \binom{N-k-1}{p-2}, $$ until $s_m \ge n$. Set $$ a_1 = F(n,N,p) := \min\{m \mid s_m\ge n\}. $$ Now repeat with $$ a_{i+1} = F(n-s_{a_i-1}, N-a_i, p-1) $$ for $i\in\{1, \ldots, p-2\}$. $a_n$ will be a slightly special (and easy) case.


EDIT:

I realized that we have the closed formula $$ s_m(N,p) = \binom{N-1}{p-1} - \binom{N-1-m}{p-1}, $$ which follows from the identity $\sum_{j=k}^n\binom jk = \binom{n+1}{k+1}$. With this, we can actually do a binary search for $m$ to speed things up.


Let's say $N=7$, $p=4$, $n=5$. Compute $$ s_1 = \binom52 = 10 \ge 5. $$ So $a_1 = 1$. Repeat with $N=6$, $p=3$, $n=5$: $$ \begin{split} s_1 &= \binom41 = 4 < 5, \\ s_2 &= s_1 + \binom31 = 7 \ge 5, \end{split}$$ So $a_2 = 2$. Repeat with $N=4$, $p=2$, $n=1$: $$ s_1 = \binom20 = 1 \ge 1 $$ So $a_3 = 1$. Repeat with $N=3$, $p=1$, $n=1$. Clearly $a_4=3$ now. So the answer is $(1,2,1,3)$.