6
$\begingroup$

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.

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.

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.

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

For $K \ll 2N/3$, a good solution goes as follows, for $K$ even (the case $K$ odd is very similar):

  1. Generate all XORs of length 2.
  2. Generate all XORs of length 3.
  3. ...
  4. Generate all XORs of length $K/2$.
  5. Generate all XORs of length $K$.

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.

You can optimize this a bit as follows:

  1. Generate all XORs of length 2 of $X_1,\ldots,X_{N-K/2+2}$.
  2. Generate all XORs of length 3 of $X_1,\ldots,X_{N-K/2+3}$.
  3. ...
  4. Generate all XORs of length $K/2$ of $X_1,\ldots,X_N$.
  5. Generate all XORs of length $K$.

The savings are not significant.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How is xor related to this? $\endgroup$
    – KWillets
    Oct 1, 2015 at 17:43
  • $\begingroup$ It isn't. The symbol the OP uses is also used for XOR. My algorithm only uses commutativity and associativity. $\endgroup$
    – Yuval Filmus
    Oct 1, 2015 at 17:53
  • $\begingroup$ An interesting thing about this problem is that divide and conquer approaches like this give good results in terms of the number of operations, but use lots of storage and can be shown by counterexample not to be optimal in time or space. Although it violates your precondition, consider the case of 6-choose-4. Since 6-choose-2 = 6-choose-4 = 15, we would first create 15 pairs, and then combine them to create the final 15 quartets for 30 operations and 15 accumulators. The iterative approach we use now only requires 24 operations and 5 accumulators to compute 6-choose-4. $\endgroup$
    – bcbrock
    Oct 2, 2015 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.