Eliminating the impossible choice

Question

I have a few problems just trying to plunge into this problem programmatically. This is not exactly what I am doing, but to simplify things, let's say we have a certain number of balls and a certain number of people. Each person must choose exactly one ball, and people can be limited by the type of ball that they can choose. The goal is to determine what options people choose after eliminating all the impossible combinations.

Example 1:

In the simple case, let's say we have two people, one red ball and one green ball. Person 1 can choose any ball, but person 2 can select only the green ball. This can be illustrated as follows:

Person 1: RG Person 2: G 

Since we know that person 2 must select the green ball, this means that person 1 cannot select this ball and therefore must select the red ball. Therefore, this can be simplified:

 Person 1: R Person 2: G 

So, in this case, we know for sure what everyone will choose.

Example 2:

Now let's add a little complexity. Now we have 4 people who need to select 2 red balls, 1 green ball and 4 blue balls. Person 1 can choose any ball, person 2 and 3 can choose red or green balls, and person 4 must choose a red ball. Thus, we have the following options:

 Person 1: RRGBBBB Person 2: RRG Person 3: RRG Person 4: RR 

Since person 4 has only one option, we know that a person must choose a red ball. Therefore, we can exclude 1 red ball from all other people:

 Person 1: RGBBBB Person 2: RG Person 3: RG Person 4: RR 

However, it is here that it becomes very complex. As we see, people 2 and 3 must choose one red and one green ball, we just don’t know which one will choose. However, since we only have one of the remaining balls left, red and green can also be excluded as an option from person 1:

 Person 1: BBBB Person 2: RG Person 3: RG Person 4: RR 

Now we can remove duplicates from each record left with the following parameters:

 Person 1: B Person 2: RG Person 3: RG Person 4: R 

We know the choice of person 1 and person 4, and person 2 and 3 have a choice between red and green.

---

To solve this problem, I loop over people, and first, if people have only one type of ball, remove that person from the array and put it in the results array (since I know what exactly this person should choose), and then delete one of this type of ball is every other person in the array, if any.

After that, it seems to me that the rule:

If there is $n number of people who all have the same number $n (or a subset of them), these parameters can be removed from all other people where $n less than the total number of people.

So, what I am doing is sorting out people again and checking out other people having the same parameters (or a subset of these options), and if this is equal to the total number of options for this person, remove them from the options for all other people.

Here is what I have so far to solve these two cases:

 // The quantity of each ball $balls = array( 'r' => 1, 'g' => 1, 'b' => 1, 'k' => 1, ); // The options available for each person $options = array( array('r', 'g', 'b', 'k'), array('r', 'g'), array('r', 'b'), array('b', 'g'), ); // Put both of these together into one array $people = []; foreach ($options as $option) { $person = []; foreach ($option as $ball_key) { $person[$ball_key] = $balls[$ball_key]; } $people[] = $person; } print_r($people); // This produces an array like: // Array // ( // [0] => Array // ( // [r] => 2 // [g] => 1 // [b] => 4 // ) // // [1] => Array // ( // [r] => 2 // [g] => 1 // ) // // [2] => Array // ( // [r] => 2 // [g] => 1 // ) // // [3] => Array // ( // [r] => 2 // ) // // ) // This will be used to hold the final result $results = []; do { // If anything changes, this needs to be set to true. Any time anything // changes we loop through everything again in case it caused a cascading // effect $has_change = false; // Step 1: // Find out if there are any people who have only one option and remove it // from the array and add it to the result and subtract one from all other // people with this option foreach ($people as $p_index => $p_options) { if (count($p_options) === 1) { $color = key($p_options); foreach ($people as $p_index_tmp => $p_options_tmp) { // It the current person, so skip it if ($p_index_tmp === $p_index) { continue; } if (isset($p_options_tmp[$color])) { // Subtract 1 from this color from this person and if zero, // remove it. if (--$people[$p_index_tmp][$color] === 0) { unset($people[$p_index_tmp][$color]); } $has_change = true; } } // Add to results array and remove from people array $results[$p_index] = array($color => 1); unset($people[$p_index]); } } // Step 2: // If there are $n number of people who all have the same $n number of // options (or a subset of them), these options can be removed // from all other people, where $n is less than the total number of people foreach ($people as $p_index => $p_options) { $num_options = array_sum($p_options); if ($num_options < count($people)) { // Look for other people with no different options from the ones // that this person has $people_with_same_options = []; foreach ($people as $p_index_tmp => $p_options_tmp) { foreach (array_keys($p_options_tmp) as $color) { if (array_search($color, array_keys($p_options)) === false) { // This color was not found in the options, so we can // skip this person. // (Make sure we break out of both foreach loops) continue 2; } } // This person has all the same options, so append to the array $people_with_same_options[] = $p_index_tmp; } // Remove these options from the other people if the number of // people with only these options is equal to the number of options if (count($people_with_same_options) === $num_options) { foreach ($people as $p_index_tmp => $p_options_tmp) { if (array_search($p_index_tmp, $people_with_same_options) === false) { foreach (array_keys($p_options) as $option) { unset($people[$p_index_tmp][$option]); $has_change = true; } } } } } } } while ($has_change === true); // Combine any remaining people into the result and sort it $results = $results + $people; ksort($results); print_r($results); 

This leads to the following result:

 Array ( [0] => Array ( [b] => 1 ) [1] => Array ( [r] => 1 [g] => 1 ) [2] => Array ( [r] => 1 [g] => 1 ) [3] => Array ( [r] => 1 ) ) 

Example 3:

This example does not work with the above code. Suppose there is 1 red ball, 1 green ball, 1 blue ball, one yellow ball and 4 people. Person 1 can choose any ball, person 2 can choose red or green, person 3 can choose green or blue, person 4 can choose red or blue.

Visually, it will look like this:

 Person 1: RGBY Person 2: RG Person 3: GB Person 4: RB 

Since 3 colors of red, green and blue are the only options for faces 2, 3 and 4, they are completely contained within these 3 people, and therefore they can be eliminated from person 1, that is, person 1 must choose yellow, If person 1 had to choose anything other than yellow, it would be impossible for other people to pick their eggs.

By introducing it into my PHP program, I have these input values:

 // The quantity of each ball $balls = array( 'r' => 1, 'g' => 1, 'b' => 1, 'y' => 1, ); // The options available for each person $options = array( array('r', 'g', 'b', 'y'), array('r', 'g'), array('r', 'b'), array('b', 'g'), ); 

However, I cannot figure out how to go through the cycle to find such cases without repeating every possible combination of people. Any ideas how to do this?

Answer 1

What I decided to do in the end was semi-brute force, but I reworked it so as not to go through each combination, so in most cases there should be much less iterations than every possible combination,

The total number of combinations is exp(2,count(balls)) (i.e. 2 ^ {types of balls}), so if we have 20 types of balls, then 1048576 different combinations of balls that we would have to check were Do we check everyone. Not only are there too many iterations, I actually finished the memory before that with only 16 ball colors.

To get every possible combination, you can use this function ( Source ):

 function getAllCombinations($balls) { // initialize by adding the empty set $results = array(array( )); foreach ($balls as $color => $number) { foreach ($results as $combination) { $results[] = array_merge(array($color), $combination); } } return $results; } 

However, if we return to our original rule:

If there are a number of n users whose number is equal to the number $ n (or a subset of them), these parameters can be removed from all other people where $ n is less than the total number of people.

as we can see, we can skip any iterations in the future if we have already exceeded the number of options $n . Please note that when we have several numbers of the same color of the ball, which are considered as several balls in this function.

As soon as we get the different possible subsets, we iterate over people to see if we have $n different people who use this subset and delete these values ​​from all other people. This is what I came up with at the end:

 /** * This just gets a sum of the number of balls a person can choose * from */ function getNumberOfOptions($person, $balls) { $n = 0; foreach ($person as $allowed_ball) { $n += $balls[$allowed_ball]; } return $n; } /** * This function finds all the subsets of the balls array that we can look for * in the people array later to remove options from them */ function getBallSubsets($balls, $max_n) { // initialize by adding the empty set $results = array(array( )); // Remove all balls that have more options than max_n foreach ($balls as $color => $number) { if ($number > $max_n) { unset($balls[$color]); } } // $n = 0; foreach ($balls as $color => $number) { foreach ($results as $combination) { // $n++; $set = array_merge(array($color), $combination); if (getNumberOfOptions($set, $balls) <= $max_n) { $results[] = $set; } } } // echo $n; exit; return $results; } function removeFromOthers($colors, $people, $skip_indexes) { foreach ($people as $p_index => $person) { if (array_search($p_index, $skip_indexes) === false) { foreach ($colors as $color) { $index = array_search($color, $person); if ($index !== false) { unset($people[$p_index][$index]); } } } } return $people; } function getOptions($people, $balls) { $ball_subsets = getBallSubsets($balls, count($people) -1); foreach ($ball_subsets as $sub) { $num_colors = count($sub); $num_people = getNumberOfOptions($sub, $balls); // Loop through people and if we find $n people with only the elements // from this subset, we can remove these elements from all other people $found = []; $found_colors = []; foreach ($people as $p_index => $person_arr) { foreach ($person_arr as $color) { // Contains another color, so skip this one if (array_search($color, $sub) === false) { continue 2; } } $found[] = $p_index; foreach ($person_arr as $color) { if (array_search($color, $found_colors) === false) { $found_colors[] = $color; } } } if (count($found) === $num_people && count($found_colors) == $num_colors) { $people = removeFromOthers($sub, $people, $found); } else { unset($found); } } return $people; } // The quantity of each ball $balls = array( 'r' => 3, 'g' => 2, 'b' => 1, 'k' => 16, ); // The options available for each person $people = array( array('r', 'g', 'b', 'k'), array('r', 'g'), array('r', 'b'), array('b', 'g'), ); print_r($people); $options = getOptions($people, $balls); print_r($options); 

This seems to work for any values ​​I tried. In the above example, we have 4 different colors of the ball (2 ^ 4 = 16 common combinations), however we only need to do 6 iterations in our getBallSubsets() function, so this is much more efficient than coarse, forcing every possible combination.

Answer 2

I prefer a more OOP-like approach. So I started from scratch. I hope everything is all right with you.

So, the following looks (admittedly) pretty ugly, and I haven't tested it with anything other than your three examples, but here it reads:

 class Ball { private $color; public function __construct($color) { $this->color = $color; } public function getColor() { return $this->color; } } class Ball_resource extends Ball { private $num_available; public function __construct($color, $number) { parent::__construct($color); $this->num_available = $number; } public function take() { $this->num_available--; } public function isExhausted() { return $this->num_available <= 0; } } class Person { /** * * @var Ball */ private $allowed_balls = array(); public function addConstraint($color) { $this->allowed_balls[$color] = new Ball($color); return $this; } public function getConstraints() { return $this->allowed_balls; } public function getNumberOfConstraints() { return count($this->allowed_balls); } /** * return true if removal was successful; false otherwise */ public function removeConstraint(Ball $ball) { // todo remove if (isset ($this->allowed_balls [$ball->getColor()])) { unset ($this->allowed_balls [$ball->getColor()]); return true; } else { // this means our puzzle isn't solvable return false; } } } class Simplifier { /** * * @var Person */ private $persons = array (); /** * * @var Ball_resource */ private $availableBalls = array (); public function addPerson(Person $person) { $this->persons[] = $person; return $this; } public function addBallRessource(Ball_resource $ball_resource) { $this->availableBalls[] = $ball_resource; return $this; } public function getChoices() { $queue = $this->persons; // shallow copy while (count($queue) > 0) { // find most constrained person(s) $numberOfConstraints = 1; // each person must have at least one constraint while (true) { $resolve_queue = array(); foreach($queue as $person) { if ($person->getNumberOfConstraints() === $numberOfConstraints) { $resolve_queue[] = $person; } } // find mutually dependent constraint groups connected with a person $first_run = true; foreach ($resolve_queue as $startPerson) { // check if we havent already been removed via dependencies if ($first_run || !self::contains($queue, $startPerson)) { $dependent_persons = $this->findMutuallyDependentPersons($startPerson, $resolve_queue); // make a set out of their combined constraints $combinedConstraints = $this->getConstraintsSet($dependent_persons); $this->adjustResources($dependent_persons); $this->removeFromQueue($dependent_persons, $queue); // substract each ball of this set from all less constrained persons $this->substractConstraintsFromLessConstrainedPersons($queue, $combinedConstraints, $numberOfConstraints); $first_run = false; continue 3; } } $numberOfConstraints++; } } return $this->persons; // has been altered implicitly } private static function contains(array $haystack, Person $needle) { foreach ($haystack as $person) { if ($person === $needle) return true; } return false; } private function findMutuallyDependentPersons(Person $startPerson, array $persons) { // add recursion $output = array(); //$output[] = $startPerson; foreach($persons as $person) { foreach ( $person->getConstraints () as $constraint ) { foreach ( $startPerson->getConstraints () as $targetConstraint ) { if ($constraint->getColor () === $targetConstraint->getColor ()) { $output [] = $person; continue 3; } } } } return $output; } private function getConstraintsSet(array $persons) { $output = array(); foreach ($persons as $person) { foreach ($person->getConstraints() as $constraint) { foreach($output as $savedConstraint) { if ($savedConstraint->getColor() === $constraint->getColor()) continue 2; } $output[] = $constraint; } } return $output; } private function substractConstraintsFromLessConstrainedPersons(array $persons, array $constraints, $constraintThreshold) { foreach ($persons as $person) { if ($person->getNumberOfConstraints() > $constraintThreshold) { foreach($constraints as $constraint) { foreach($this->availableBalls as $availableBall) { if ($availableBall->isExhausted()) { $person->removeConstraint($constraint); } } } } } } private function adjustResources(array $persons) { foreach($persons as $person) { foreach($person->getConstraints() as $constraint) { foreach($this->availableBalls as &$availableBall) { if ($availableBall->getColor() === $constraint->getColor()) { $availableBall->take(); } } } } } private function removeFromQueue(array $persons, array &$queue) { foreach ($persons as $person) { foreach ($queue as $key => &$availablePerson) { if ($availablePerson === $person) { unset($queue[$key]); } } } } } 

All this is called like this:

 // Example 2 { $person1 = new Person(); $person1->addConstraint("R")->addConstraint("R")->addConstraint("G")->addConstraint("B")->addConstraint("B")->addConstraint("B")->addConstraint("B"); $person2 = new Person(); $person2->addConstraint("R")->addConstraint("R")->addConstraint("G"); $person3 = new Person(); $person3->addConstraint("R")->addConstraint("R")->addConstraint("G"); $person4 = new Person(); $person4->addConstraint("R")->addConstraint("R"); $redBalls = new Ball_resource("R", 2); $greenBalls = new Ball_resource("G", 1); $blueBalls = new Ball_resource("B", 4); $simplifier = new Simplifier(); $simplifier->addPerson($person1)->addPerson($person2)->addPerson($person3)->addPerson($person4); $simplifier->addBallRessource($redBalls)->addBallRessource($greenBalls)->addBallRessource($blueBalls); $output = $simplifier->getChoices(); print_r($output); } 

And similarly for example 3:

 // Example 3 { $person1 = new Person(); $person1->addConstraint("R")->addConstraint("G")->addConstraint("B")->addConstraint("Y"); $person2 = new Person(); $person2->addConstraint("R")->addConstraint("G"); $person3 = new Person(); $person3->addConstraint("G")->addConstraint("B"); $person4 = new Person(); $person4->addConstraint("R")->addConstraint("B"); $redBalls = new Ball_resource("R", 1); $greenBalls = new Ball_resource("G", 1); $blueBalls = new Ball_resource("B", 1); $yellowBalls = new Ball_resource("Y", 1); $simplifier = new Simplifier(); $simplifier->addPerson($person1)->addPerson($person2)->addPerson($person3)->addPerson($person4); $simplifier->addBallRessource($redBalls)->addBallRessource($greenBalls)->addBallRessource($blueBalls)->addBallRessource($yellowBalls); $output = $simplifier->getChoices(); print_r($output); } 

I have reduced the original output for brevity. But for the second example, it is essentially equal to your last relevant listing in the question, and for example 3 it gives the equivalent:

 Person 1: Y Person 2: RG Person 3: GB Person 4: RB