Устранение невозможного выбора

У меня есть небольшая проблема, просто пытаюсь обернуть голову вокруг этой проблемы программно. Это не совсем то, что я делаю, но чтобы упростить вещи, скажем, у нас есть определенное количество шаров и определенное количество людей. Каждый человек должен выбери ровно один мяч и народ может ограничиваться типом мяча, который они могут выбрать. Цель состоит в том, чтобы определить, какие варианты люди должны выбрать после устранения всех невозможных комбинаций.

Пример 1:

В простом случае, скажем, у нас есть два человека и один красный шар и один зеленый шар. Человек 1 может выбрать любой шар, но человек 2 может выбрать только зеленый шар. Это можно проиллюстрировать как:

Person 1: RG
Person 2: G

Поскольку мы знаем, что человек 2 должен выбрать зеленый шар, это означает, что человек 1 не может выбрать этот шар и поэтому должен выбрать красный шар. Так что это может быть упрощено до:

Person 1: R
Person 2: G

Так что в этом случае мы точно знаем, что выберет каждый человек.

Пример 2:

Теперь давайте добавим немного сложности. Теперь у нас есть 4 человека, которые должны выбрать из 2 красных шаров, 1 зеленый шар и 4 синих шара. Человек 1 может выбрать любой шар, человек 2 и 3 могут выбрать красные или зеленые шары, а человек 4 должен выбрать красный шар. Итак, у нас есть следующие варианты:

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

Поскольку у человека 4 есть только один тип опций, мы знаем, что этот человек должен выбрать красный шар. Поэтому мы можем устранить 1 красный шар от всех других людей:

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

Однако это то, где это становится действительно сложным. Как мы видим, люди 2 и 3 должны выбрать один красный и один зеленый шар, мы просто не знаем, какой из них выберет какой. Однако, так как у нас остается только 1 из каждого шара, красный и зеленый также могут быть исключены как опция от лица 1:

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

Теперь мы можем удалить дубликаты из каждой записи, оставив следующие параметры:

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

Мы знаем выбор человека 1 и человека 4, а у людей 2 и 3 есть выбор между красным и зеленым.

---

Чтобы решить эту проблему, я делаю цикл над людьми, и сначала, если у людей есть только один тип мяча, удалите этого человека из массива и поместите его в массив результатов (так как я знаю, что именно этот человек должен выбрать), а затем удалите один шарик этого типа из любого другого человека в массиве, если он есть.

После этого мне кажется, что правило таково:

Если есть $n количество людей, у которых все одинаковые $n количество
параметры (или их подмножество), эти параметры могут быть удалены
от всех других людей, где $n меньше, чем общее количество людей.

Поэтому я снова проверяю людей и проверяю, есть ли у них те же параметры (или подмножество этих параметров), и, если оно равно общему количеству параметров для этого человека, удалите их из параметров для все остальные люди.

Вот что у меня есть, что решит эти два случая:

// 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's 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);

Это дает следующий результат:

Array
(
[0] => Array
(
[b] => 1
)

[1] => Array
(
[r] => 1
[g] => 1
)

[2] => Array
(
[r] => 1
[g] => 1
)

[3] => Array
(
[r] => 1
)

)

Пример 3:

Этот пример не работать с приведенным выше кодом. Предположим, что есть 1 красный шар, 1 зеленый шар, 1 синий шар, один желтый шар и 4 человека. Человек 1 может выбрать любой шар, человек 2 может выбрать красный или зеленый, человек 3 может выбрать зеленый или синий, человек 4 может выбрать красный или синий.

Визуально это будет выглядеть так:

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

Поскольку 3 цвета — красный, зеленый и синий — являются единственными вариантами для лиц 2, 3 и 4, они полностью содержатся в этих 3 людях и поэтому могут быть исключены из лица 1, то есть человек 1 должен выбрать желтый. Если бы человек 1 выбрал что-то кроме желтого, другие люди не смогли бы выбрать свои шары.

Поместив его в мою программу PHP, у меня есть эти входные значения:

// 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'),
);

Однако я не могу придумать, как пройтись по циклам, чтобы найти подобные случаи, не перебирая все возможные комбинации людей. Есть идеи, как это можно сделать?

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]);
}
}
}
}
}

// 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);
}

// 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);
}

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

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;
}

/**
* 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);