Thanks for looking at my question.

This is a problem I am trying to solve to create a software application which can make chains of connections between parts in a physical system. I will try to boil it down to common combinatorical parlance.

  • There are 4 bins and 4 numbered balls.
  • There's a max of one ball per bin.
  • Some bins are required to have a ball in them, some are not.
  • Each individual bin has certain numbered balls that are allowed to go in the bin. Another way of stating this is that only certain balls are "compatible" with each bin. This compatibility is fixed and does not change.

The system is in any intermediate state of ball assignment, which could be anywhere from no balls assigned to only one ball left. For each bin, generate a list of which of the remaining balls is eligible to go in the bin.

I also would appreciate someone telling me what math adjectives describe this type of problem so that I may better study it or similar example problems.

Thank you!

Related comment 1:
I believe it is possible to brute-force this problem by assigning balls one at a time and making all possible permutations of ball choices, within the rules established. Take the ball position results of each permutation and make a list of what balls ended up in what bins. Then you have a list of which remaining balls could have gone in each bin, and that is the answer we are after.

For example, you could order the bins starting with ones that require a ball and ending with ones that do not require a ball. Then, begin assigning balls in order. Start with the first ordered bin, and pick one of its allowable balls. Then, move to the second bin, and pick one of its allowable balls from the remaining balls. Do this until you're finished with all bins. That's one permutation. Now, start over and make different ball choices. Repeat until you've exhausted all possible choices. Finally, superimpose the final ball positions from each permutation on top of each other and for each bin you will now have a list of balls that could end up in it.

The only problem with this is that I believe it will be computationally prohibitive for the problem sizes my program will have to handle. That is why I'd like to know if there are any mathematical set theory / combinatoric tricks that could be applied to avoid having to brute force the problem.

  • $\begingroup$ Not every ball has to be in a bin then? $\endgroup$ – Tunococ Sep 7 '12 at 5:35
  • $\begingroup$ Correct, not every ball has to be in a bin. $\endgroup$ – Shaun Sep 7 '12 at 5:55
  • 1
    $\begingroup$ Can you clarify the question? I think as it stands it makes no sense. What do you mean by "arbitrary subset"? Is it fixed? Why isn't the answer "any ball left in this subset"? $\endgroup$ – user641 Sep 7 '12 at 6:03
  • $\begingroup$ Thanks for taking the time to respond. By "arbitrary subset" I mean any mixture of ball numbers could be allowed. It is fixed. The answer isn't "any ball left in this subset" because if another bin is required to be filled, it could rob any of the subset balls. This would mean that a ball in the subset actually is no longer available. $\endgroup$ – Shaun Sep 7 '12 at 6:08
  • $\begingroup$ The title of the question is inappropriate. Rather than giving a glimpse into the problem, you state it as a tough one. This biases one's intuitive thinking and makes one be on guard which is not healthy for a problem solver. Never state a problem as tough beforehand. You can't know it's tough unless you have tried it but assuming it's tough before you begin meddles with the natural thinking process and approach. $\endgroup$ – ajay Sep 7 '12 at 6:46

Here is a very similar problem stated in logical matrix form. But, in this case there can be more than one of each numbered ball (to stick with my analogy). https://stackoverflow.com/questions/9500657/matlab-get-all-permutations-for-a-specific-logical-matrix

Also, an answer on that question points the user to this matlab code called "allcomb" which can do the calculation. Again, there can be more than one of each ball. http://www.mathworks.com/matlabcentral/fileexchange/10064-allcomb

Here is a clearer explanation of how to brute force the problem. First, find all of the permutations of allowable ball distribution into the buckets which are required to have balls in them. For each of these permutations, do a permutation of the non-ball-requiring bins with the remaining balls. Combine the permutations. The full set of these reveals which balls can end up in which buckets according to the diverse rule set.


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.