排除不可能的选择
Eliminating impossible choices
我在尝试以编程方式解决这个问题时遇到了一些麻烦。这不是我正在做的，但为了简化事情，假设我们有一定数量的球和一定数量的人。每个人 必须 只选择一个球，并且人们 可以 限于他们可以选择的球类型。 objective是在排除所有不可能的组合后，决定人们必须选择的选项。
示例 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有红色和绿色的选择。
为了解决这个问题，我所做的是遍历人，首先如果人只有一种球类型，则从数组中删除那个人并将其放入结果数组中（因为我知道那是那个人必须选择）然后从阵列中的每个其他人中删除该球类型之一（如果存在）。
在此之后，我觉得规则是：
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.
所以我所做的是再次遍历这些人并检查其他人是否有相同的可用选项（或这些选项的子集），如果这等于该人的选项总数，则删除他们来自所有其他人的选项。
这是我目前所掌握的可以解决这两种情况的方法：
// 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 个蓝球、1 个黄球和 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'),
);
但是我想不出如何在不遍历每个可能的人组合的情况下循环查找这样的案例。知道如何做到这一点吗？
我更喜欢 OOP-like 的方法。所以我基本上是从头开始的。我希望你没问题。
所以，下面看起来（无可否认）非常难看，除了你的三个例子，我还没有用任何东西测试过它，但在这里：
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);
}
对于示例 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);
}
为简洁起见，我省略了原始输出。但对于第二个示例，它基本上等于您在问题中最后列出的相应列表，对于示例 3，它产生的等价物为：
Person 1: Y
Person 2: RG
Person 3: GB
Person 4: RB
我最后决定做的是 semi 蛮力，但是我对其进行了调整，这样它就不必经过每一个组合，所以在大多数情况下在某些情况下，迭代次数应该比每个可能的组合少 far 次。
组合总数等于 exp(2,count(balls))（即 2^{球的类型}），因此如果我们有 20 种球，那么我们将需要检查 1048576 种不同的球组合如果我们要检查每一个。不仅迭代次数太多，我实际上 运行 在此之前只有 16 种球颜色，我的内存不足。
要获得所有可能的组合，您可以使用此函数 (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;
}
然而，如果我们回到原来的规则：
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.
正如我们所见，如果我们已经超过 $n 个选项，我们可以跳过任何未来的迭代。注意，当我们有多个相同颜色的球时，在此函数中算作多个球。
一旦我们得到不同的可能值 sub-sets，我们就会遍历这些人，看看是否有 $n 不同的人使用该子集，然后从所有其他人那里删除这些值。这是我最后想到的：
/**
* 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);
这似乎适用于我尝试过的任何值。在上面的例子中，我们有 4 种不同的球颜色（2^4 = 16 种组合），但是我们只需要在我们的 getBallSubsets() 函数中进行 6 次迭代，所以这比暴力强制每一种可能的方法更有效组合.
我在尝试以编程方式解决这个问题时遇到了一些麻烦。这不是我正在做的，但为了简化事情，假设我们有一定数量的球和一定数量的人。每个人 必须 只选择一个球，并且人们 可以 限于他们可以选择的球类型。 objective是在排除所有不可能的组合后，决定人们必须选择的选项。
示例 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有红色和绿色的选择。
为了解决这个问题，我所做的是遍历人，首先如果人只有一种球类型，则从数组中删除那个人并将其放入结果数组中（因为我知道那是那个人必须选择）然后从阵列中的每个其他人中删除该球类型之一（如果存在）。
在此之后，我觉得规则是：
If there are
$nnumber of people who all have the same$nnumber of options (or a subset of them), these options can be removed from all other people, where$nis less than the total number of people.
所以我所做的是再次遍历这些人并检查其他人是否有相同的可用选项（或这些选项的子集），如果这等于该人的选项总数，则删除他们来自所有其他人的选项。
这是我目前所掌握的可以解决这两种情况的方法：
// 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 个蓝球、1 个黄球和 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'),
);
但是我想不出如何在不遍历每个可能的人组合的情况下循环查找这样的案例。知道如何做到这一点吗？
我更喜欢 OOP-like 的方法。所以我基本上是从头开始的。我希望你没问题。
所以，下面看起来（无可否认）非常难看，除了你的三个例子，我还没有用任何东西测试过它，但在这里：
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);
}
对于示例 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);
}
为简洁起见，我省略了原始输出。但对于第二个示例，它基本上等于您在问题中最后列出的相应列表，对于示例 3，它产生的等价物为：
Person 1: Y
Person 2: RG
Person 3: GB
Person 4: RB
我最后决定做的是 semi 蛮力，但是我对其进行了调整，这样它就不必经过每一个组合，所以在大多数情况下在某些情况下，迭代次数应该比每个可能的组合少 far 次。
组合总数等于 exp(2,count(balls))（即 2^{球的类型}），因此如果我们有 20 种球，那么我们将需要检查 1048576 种不同的球组合如果我们要检查每一个。不仅迭代次数太多，我实际上 运行 在此之前只有 16 种球颜色，我的内存不足。
要获得所有可能的组合，您可以使用此函数 (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;
}
然而，如果我们回到原来的规则：
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.
正如我们所见，如果我们已经超过 $n 个选项，我们可以跳过任何未来的迭代。注意，当我们有多个相同颜色的球时，在此函数中算作多个球。
一旦我们得到不同的可能值 sub-sets，我们就会遍历这些人，看看是否有 $n 不同的人使用该子集，然后从所有其他人那里删除这些值。这是我最后想到的：
/**
* 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);
这似乎适用于我尝试过的任何值。在上面的例子中，我们有 4 种不同的球颜色（2^4 = 16 种组合），但是我们只需要在我们的 getBallSubsets() 函数中进行 6 次迭代，所以这比暴力强制每一种可能的方法更有效组合.