0
$\begingroup$

I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative state.

Does anyone know what the best way would be to calculate the full set of combination values that fits this constraint?

Right now I just implemented a simple counting algorithm, but that will take forever since I have to test if there are n positive and negative variables at 3^64 levels, and that is before I even start to evaluate the weighting term I am actually interested in.

|cite|improve this question
$\endgroup$
  • $\begingroup$ "all possible combinations of variables such that I have n variables in each the positive and negative state" Do you mean the number of all possible combinations of values in each of which there are $n$ positive values and $n$ negative values? It might not be possible to record or show all those combinations, since there might be too many of them. $\endgroup$ – John L. Apr 10 '19 at 0:55
  • $\begingroup$ As your comment shows, you were stating the wrong problem in this question. The right problem might be something like "how do I generate two random disjoint subsets of $n$ variables out of a set of 64 variables?". I would encourage you to ask a new question since this question could be used as it is. In your new question, please include the background and motivation as stated in that comment. $\endgroup$ – John L. Apr 10 '19 at 3:51
1
$\begingroup$

There will be ${64 \choose n} \cdot {64-n \choose n}$ such combinations, since there are ${64 \choose n}$ ways to choose a subset of $n$ of the 64 variables to be -1, and then ${64-n \choose n}$ ways to choose a subset of $n$ of the $64-n$ remaining variables to be 1. Equivalently, this is ${64! \over n!^2 (64-2n)!}$.

You probably won't want to explicitly generate all of those combinations, as it would take exponentially long to do so (as there are exponentially many such combinations).

But if you really wanted to explicitly enumerate all combinations, this formula also highlights the way to do that. First, enumerate all possible ways to choose $n$ of the 64 variables; there are standard algorithms for how to do that (e.g., https://stackoverflow.com/q/127704/781723, https://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations). Then, for each such, enumerate all possible ways to choose $n$ of the remaining $64-n$ variables (again, using the same algorithm). That will give you all ways to choose a combination of the sort you desire.

Still, any time you are enumerating exponentially many possibilities and then doing something to each, you should check whether maybe there's a better way to achieve your ultimate goal without enumerating all of them. If you want to find the combination that minimizes some cost function, there might be a better way to do that, depending on the cost function.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hi, thank you both. Your answer is useful for knowing the total number of combinations, but what if I want to generate each valid combination in a reasonably efficient manner? I realize that this will be computationally intensive, but I plan to use a value for n that isn't too big. $\endgroup$ – Erik Lee Apr 10 '19 at 2:38
  • $\begingroup$ @ErikLee I'm still not sure how practical it is, even with $n =1$ you have 4000+ possibilities. At $n = 5$ you're already running over the memory of most computers not including the size of the sequence itself. If you kept it to $n \leq 4$ then it might be practical. $\endgroup$ – ryan Apr 10 '19 at 2:52
  • 1
    $\begingroup$ @ErikLee The real question is why do you want all possible combinations? Is it just to print them all out? If there is some other purpose, we might be able to help you avoid checking them all explicitly. $\endgroup$ – ryan Apr 10 '19 at 2:55
  • $\begingroup$ @ryan, thanks for your reply. This is for a design application. I am considering a problem where I have 64 variables that can either be 0/-1/1, and for all the combinations that fit the criteria I mentioned above (n positive and n negative values), I will evaluate some cost function. So I do not need all combinations in advance and would ideally be calculating them in some efficient way on the fly. $\endgroup$ – Erik Lee Apr 10 '19 at 3:04
  • $\begingroup$ All, please check my last comment to the question. $\endgroup$ – John L. Apr 10 '19 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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