Not sure if this is a proper place, but I really don't know where else to ask. I'm craving for an algorithm generating certain sequences of numbers (the problem comes from physics).
I'm looking for all such sequences of $a_n$ an $b_n$ that: $$ \begin{cases} \sum \limits_{n=1}^{K} (n a_n) + \sum \limits_{m=1}^{K} (m b_m) = K\\ \sum \limits_{n=1}^{K} a_n - \sum \limits_{m=1}^{K} b_m = Q\\ \end{cases} \quad,\quad \text{where}\qquad \begin{cases} K\in\mathbb{Z}^+\\ Q\in\mathbb{Z}\\ a_n,b_m= \{0,1\} \end{cases} $$
For my application, I am interested in finding all such sequences starting from $K=Q(\operatorname{mod}2)$ and up to some large value of $K$, so, I guess, it would make sense to solve the problem iteratively. I would really appreciate if someone could up with an efficient solution.
EXAMPLE
For $Q=0$, $K=2$ the only option is $a_1=b_2=1$. We shall write it as $\{\{1\},\{1\}\}$. The first sublist corresponds to $a$'s, the second $-$ to $b$'s. The $j$th position in the sublist denotes the value of $a_j$ or $b_j$.
For $Q=0$, $K=4$, the possible sets are: $\{a_3=1;b_1=1\}$, $\{a_1=1;b_3=1\}$, $\{a_2=1;b_2=1\}$, with all other coefficients vanishing.
Here's an example of the output: \begin{alignat}{9} &Q=0,K=2:\quad &&\{\{\{1\},\{1\}\}\}\\ &Q=0,K=4:\quad &&\{\{\{0,0,1\},\{1\}\},\{\{1\},\{0,0,1\}\},\{\{0,1\},\{0,1\}\}\} \\&...&& \end{alignat}
Where I omitted the vanishing elements following the last non-zero element.
P.S.
The particular form of the output is not important for me. I would be equally happy to get it, say, in the form of lists of numbers of non-vanishing elements: \begin{alignat}{9} &Q=0,K=2:\quad &&\{\{\{1\},\{1\}\}\}\\ &Q=0,K=4:\quad &&\{\{\{3\},\{1\}\},\{\{1\},\{3\}\},\{\{2\},\{2\}\}\} \\&...&& \end{alignat}
UPDATE
By efficient algorithm I mean the one which does not make any useless steps (like "going though all possible sequences and throwing away the ones which do not work"). Yes, the algorithm will work in exponential time, and there's nothing we can do about it.
I think, a friend of mine came up with a solution.
At the first step, we generate the table having $K$ rows which contains all the partitions of $k=1..K$ into $m$ different terms:
$$ \begin{pmatrix} \{1\} & & \\ \{2\} & & \\ \{3\} & \{1,2\} &\\ \{4\} & \{1,3\} &\\ \{5\} & \{1,4\},\{2,3\} &\\ \{6\} & \{1,5\},\{2,4\},\{3,3\} & \{1,2,3\} \end{pmatrix} $$
Then, we consider all the possible ways to split $K=K_1+K_2$. For each pair $\{K_1,K_2\}$, we consider partitions of $K_1$ and $K_2$ having $n_1$ and $n_2$ elements, correspondingly. Of those, we are interested only in such that $n_1-n_2 = Q$.
I'm wondering if anyone could help with writing the pseudocode for this solution? I'm too stupid to deal with all the For's... I feel like it should look smth like this:
for (all partitions of K into K1 and K2)
for (all lengths of partitions of K1)
for (all partitions of K1 of given length)
for (all partitions of K2 having the length (Q-current length of K1 partition) )
take the current partitions!
end
end
end
end
MOTIVATION
For the curious ones: the problem is motivated by representing the fermionic part of the system considered in this paper, see eq. (3.5).
In two dimensions, the state of the system containing fermions and neutral bosons is described by a list of numbers saying how many particles of each sort with given momentum we have: $$ |n_1,n_2,\ldots,n_N; \overline{n}_1,\overline{n}_2,\ldots,\overline{n}_{\overline{N}}; \widetilde{n}_1^{\widetilde{m}_1},\widetilde{n}_2^{\widetilde{m}_2},\ldots,\widetilde{n}_{\widetilde{N}}^{\widetilde{m}_{\widetilde{N}}}\rangle $$ Here $n_k$ is the number of fermions with momentum $k$, $\overline{n}_k$ is the number of anti-fermions with momentum $k$. Both can be either $0$ or $1$, due to the Pauli exclusion principle (or, better say, due to the spin-statistics theorem). As for bosons of each momentum, we can have an arbitrary number of those. The momenta are discretized due to the fact that the system is considered on a finite interval of space (much like in the case of the Fourier series). The momenta are positive because we are in the light-cone coordinates: if you are an observer is flying to the left with the speed of light, all the massive particles seem for you to be right-movers. We are interested in finding all the states with a given charge (the difference between the numbers of fermions and anti-fermions) and total momentum (the sum of momenta of all the particles in the state).
The first step is trivial, the total momentum can be separated into momenta of the bosonic and fermionic parts. Here I only asked about the latter, since the former is trivially given by all possible partitions of an integer.