Time/Space Optimal k-Subset Operator Application - Is this a named problem? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:47:36Z https://cs.stackexchange.com/feeds/question/47774 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/47774 6 Time/Space Optimal k-Subset Operator Application - Is this a named problem? bcbrock https://cs.stackexchange.com/users/40479 2015-10-01T14:53:49Z 2015-10-01T17:18:07Z <p>I have searched extensively and unsuccessfully for references to a combinatorial problem that arises in my work. I am hoping someone can tell me if this type of problem has a "name" and provably optimal solutions.</p> <p>The problem: Given a set of objects denoted by $X_1,\ldots,X_N$, a commutative and associative operator $\oplus$, and $K \leq N$, generate all $N \choose K$ subset-applications of the operator in a way that first minimizes the number of operator applications, and then minimizes the number of partial results that must be stored, assuming that once a complete combination is generated its storage can be recovered. For example, for $5 \choose 4$ we need to generate the five new objects $$X_1 \oplus X_2 \oplus X_3 \oplus X_4, \\ X_1 \oplus X_2 \oplus X_3 \oplus X_5, \\ X_1 \oplus X_2 \oplus X_4 \oplus X_5, \\ X_1 \oplus X_3 \oplus X_4 \oplus X_5, \\ X_2 \oplus X_3 \oplus X_4 \oplus X_5 \\$$ which naively requires 15 operator applications and a single accumulator. However a better solution requires only 11 operator applications if storage is allocated for 3 partial results.</p> <p>Note that no negation or inverse of the operator $\oplus$ is assumed. This rules out using most popular combination-generation schemes such as Gray codes. In the motivating application the operator is also idempotent ($X \oplus X = X$) but I don't think this fact is helpful to a solution.</p> <p>I have developed a good algorithm to solve the problem using at most $N$ accumulators. However it strikes me that others have probably analyzed this type of problem and I simply don't know the correct terminology to guide my search.</p> https://cs.stackexchange.com/questions/47774/-/47781#47781 1 Answer by Yuval Filmus for Time/Space Optimal k-Subset Operator Application - Is this a named problem? Yuval Filmus https://cs.stackexchange.com/users/683 2015-10-01T17:18:07Z 2015-10-01T17:18:07Z <p>For $K \ll 2N/3$, a good solution goes as follows, for $K$ even (the case $K$ odd is very similar):</p> <ol> <li>Generate all XORs of length 2.</li> <li>Generate all XORs of length 3.</li> <li>...</li> <li>Generate all XORs of length $K/2$.</li> <li>Generate all XORs of length $K$.</li> </ol> <p>This requires $\binom{N}{K/2} + \binom{N}{K/2-1} \approx \binom{N}{K/2}$ memory and $\binom{N}{2} + \cdots + \binom{N}{K/2} + \binom{N}{K} \approx \binom{N}{K}$ operations. This is close to optimal in terms of number of operations, since clearly at least $\binom{N}{K}$ are needed.</p> <p>You can optimize this a bit as follows:</p> <ol> <li>Generate all XORs of length 2 of $X_1,\ldots,X_{N-K/2+2}$.</li> <li>Generate all XORs of length 3 of $X_1,\ldots,X_{N-K/2+3}$.</li> <li>...</li> <li>Generate all XORs of length $K/2$ of $X_1,\ldots,X_N$.</li> <li>Generate all XORs of length $K$.</li> </ol> <p>The savings are not significant.</p>