我试图以编程方式解决这个问题时遇到了一些麻烦.这不是我正在做的事情,但为了简化事情,我们说有一定数量的球和一定数量的人.每个人必须选择一个球,人们可能只限于他们可以选择的球类型.目标是确定在消除所有不可能的组合后人们必须选择的选项.
例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'),'b'),array('b',);
// 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个人.人1可以选择任何球,人2可以选择红色或绿色,人3可以选择绿色或蓝色,人4可以选择红色或蓝色.
在视觉上这看起来像：
Person 1: RGBY Person 2: RG Person 3: GB Person 4: RB
由于红色,绿色和蓝色3种颜色是2,3和4人的唯一选择,因此它们完全包含在这3个人中,因此它们都可以从人1中消除,这意味着人1必须选择黄色.如果第一个人选择黄色的东西,那么其他人就不可能选择他们的球.
把它放到我的PHP程序中,我有这些输入值：
// The quantity of each ball
$balls = array(
'r' => 1,'y' => 1,'y'),);
但是我想不出如何循环查找这样的案例而不迭代每个可能的人组合.有什么想法可以做到这一点？
我更喜欢采用类似OOP的方法.所以我基本上从头开始.我希望你没关系.
所以,以下看起来(不可否认)非常丑陋,除了你的三个例子之外,我还没有测试过它,但是在这里：
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);
$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
