3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Does $f$ have any particular properties? Linearity? Something else? $\endgroup$
    – orlp
    Commented Apr 29 at 7:52
  • $\begingroup$ If $r$ can be equal to $N$, why is $X_{r,k}$ a proper subset of $A$? $\endgroup$ Commented Apr 29 at 12:22
  • $\begingroup$ @ZiadIsmailiAlaoui my bad, it was a typo $\endgroup$
    – GeoArt
    Commented Apr 29 at 15:42
  • $\begingroup$ @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. $\endgroup$
    – GeoArt
    Commented Apr 29 at 15:46

1 Answer 1

1
$\begingroup$

In The Coolest Way to Generate Combinations by Frank Ruskey and Aaron Williams the authors describe a method to iterate over all combinations of a set such that at most two elements are added or removed from the set per iteration. The algorithm is also loopless, each set is generated from the last in a constant number of operations.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – GeoArt
    Commented Apr 29 at 16:29
  • $\begingroup$ @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. $\endgroup$
    – orlp
    Commented Apr 29 at 16:58
  • $\begingroup$ @GeoArt See Donald Knuth, The Art of Computer Programming, Volume 4A, 7.2.1.1, Algorithm L for example. $\endgroup$
    – orlp
    Commented Apr 29 at 17:01

Your Answer

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

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