# Best algorithm to evaluate a function that takes the elements of all possible combinations of N numbers

Consider a set $$A$$ containing $$N$$ real numbers. Let $$f(X_{r,k})$$ represent a function, where $$X_{r,k}\subseteq A$$ denotes the $$k$$th combination of $$r$$ elements from $$A$$, with $$1 \leq k \leq \binom{N}{r}$$ and $$0 \leq r \leq N$$. What is the most efficient method to compute $$f(X_{r,k})$$ for all possible values of $$r$$ and $$k$$?

Since the number of possible $$k$$s is maximal when $$r= \lfloor N/2\rfloor$$, one could start by evaluating those combinations and then using them as seeds to sequentially add and remove smaller ones, making use of the symmetry given by the fact that for a given $$X_{r,k}$$ there is a $$X_{N-r,k'}$$ such that $$X_{r,k}\cup X_{N-r,k'}=A$$.

Is this suggestion sensible? Can it be further optimized? Is there an altogether better approach?

• Does $f$ have any particular properties? Linearity? Something else?
– orlp
Commented Apr 29 at 7:52
• If $r$ can be equal to $N$, why is $X_{r,k}$ a proper subset of $A$? Commented Apr 29 at 12:22
• @ZiadIsmailiAlaoui my bad, it was a typo Commented Apr 29 at 15:42
• @orlp I would like to make it work for an arbitrary $f$. However, if it helps, I'm looking for the smallest linear combination of elements in $X$ according to some rules to assign coefficients. Commented Apr 29 at 15:46

• Thank you. But my understanding of the paper is that it will, very efficiently, generate the combinations for a fixed $r$. My concern is more about navigating across the space of all possible values of $r$. Commented Apr 29 at 16:29
• @GeoArt I mean if $r$ isn't fixed then you're just looking at the powerset. Iterating over this while only adding one new element and removing one old element per iteration is also known as a Gray code. There are also loopless algorithms for Gray codes.