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.