php – 消除不可能的选择

PHP 前端之家
前端之家收集整理的这篇文章主要介绍了php – 消除不可能的选择，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
我试图以编程方式解决这个问题时遇到了一些麻烦.这不是我正在做的事情,但为了简化事情,我们说有一定数量的球和一定数量的人.每个人必须选择一个球,人们可能只限于他们可以选择的球类型.目标是确定在消除所有不可能的组合后人们必须选择的选项.

例1：

在一个简单的例子中,说我们有两个人,一个红球和一个绿球.人1可以选择任一球,但是人2只能选择绿球.这可以说明如下：

  1. Person 1: RG
  2. Person 2: G

因为我们知道人2必须选择绿球,这意味着人1不能选择那个球,因此必须选择红球.所以这可以简化为：

  1. Person 1: R
  2. Person 2: G

所以在这种情况下,我们确切地知道每个人会选择什么.

例2：

现在让我们添加一些复杂性.现在我们有4个人需要从2个红球,1个绿球和4个蓝球中选择.人1可以选择任何球,人2和3可以选择红色或绿色球,人4必须选择红色球.所以我们有以下选择：

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

由于人4只有一种选择,我们知道那个人必须选择一个红球.因此,我们可以从所有其他人中消除1个红球：

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

然而,这是它变得非常棘手的地方.我们可以看到,第2和第3人必须选择一个红球和一个绿球,我们只是不知道哪一个会选择哪一个.但是,由于我们每个球只剩下1个,因此红色和绿色也可以作为选项从第1个人中删除：

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

现在,我们可以使用以下选项从每个条目中删除重复项：

  1. Person 1: B
  2. Person 2: RG
  3. Person 3: RG
  4. 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.

所以我所做的就是再次遍历所有人,并检查具有相同选项的其他人(或这些选项的子集),如果这等于该人的选项总数,请从选项中删除所有其他人.

这是我到目前为止解决这两种情况的方法：

  1. // The quantity of each ball
  2. $balls = array(
  3.     'r' => 1,'g' => 1,'b' => 1,'k' => 1,);
  4. // The options available for each person
  5. $options = array(
  6.     array('r','g','b','k'),array('r','g'),'b'),array('b',);
  7.  
  8. // Put both of these together into one array
  9. $people = [];
  10. foreach ($options as $option) {
  11.     $person = [];
  12.     foreach ($option as $ball_key) {
  13.         $person[$ball_key] = $balls[$ball_key];
  14.     }
  15.     $people[] = $person;
  16. }
  17.  
  18. print_r($people);
  19. // This produces an array like:
  20. // Array
  21. // (
  22. //     [0] => Array
  23. //         (
  24. //             [r] => 2
  25. //             [g] => 1
  26. //             [b] => 4
  27. //         )
  28. //
  29. //     [1] => Array
  30. //         (
  31. //             [r] => 2
  32. //             [g] => 1
  33. //         )
  34. //
  35. //     [2] => Array
  36. //         (
  37. //             [r] => 2
  38. //             [g] => 1
  39. //         )
  40. //
  41. //     [3] => Array
  42. //         (
  43. //             [r] => 2
  44. //         )
  45. //
  46. // )
  47.  
  48. // This will be used to hold the final result
  49. $results = [];
  50.  
  51. do {
  52.     // If anything changes,this needs to be set to true. Any time anything
  53.     // changes we loop through everything again in case it caused a cascading
  54.     // effect
  55.     $has_change = false;
  56.  
  57.     // Step 1:
  58.     // Find out if there are any people who have only one option and remove it
  59.     // from the array and add it to the result and subtract one from all other
  60.     // people with this option
  61.     foreach ($people as $p_index => $p_options) {
  62.         if (count($p_options) === 1) {
  63.             $color = key($p_options);
  64.  
  65.             foreach ($people as $p_index_tmp => $p_options_tmp) {
  66.                 // It's the current person,so skip it
  67.                 if ($p_index_tmp === $p_index) {
  68.                     continue;
  69.                 }
  70.  
  71.                 if (isset($p_options_tmp[$color])) {
  72.                     // Subtract 1 from this color from this person and if zero,// remove it.
  73.                     if (--$people[$p_index_tmp][$color] === 0) {
  74.                         unset($people[$p_index_tmp][$color]);
  75.                     }
  76.  
  77.                     $has_change = true;
  78.                 }
  79.             }
  80.  
  81.             // Add to results array and remove from people array
  82.             $results[$p_index] = array($color => 1);
  83.             unset($people[$p_index]);
  84.         }
  85.     }
  86.  
  87.     // Step 2:
  88.     // If there are $n number of people who all have the same $n number of
  89.     // options (or a subset of them),these options can be removed
  90.     // from all other people,where $n is less than the total number of people
  91.     foreach ($people as $p_index => $p_options) {
  92.         $num_options = array_sum($p_options);
  93.         if ($num_options < count($people)) {
  94.             // Look for other people with no different options from the ones
  95.             // that this person has
  96.             $people_with_same_options = [];
  97.             foreach ($people as $p_index_tmp => $p_options_tmp) {
  98.                 foreach (array_keys($p_options_tmp) as $color) {
  99.                     if (array_search($color,array_keys($p_options)) === false) {
  100.                         // This color was not found in the options,so we can
  101.                         // skip this person.
  102.                         // (Make sure we break out of both foreach loops)
  103.                         continue 2;
  104.                     }
  105.                 }
  106.                 // This person has all the same options,so append to the array
  107.                 $people_with_same_options[] = $p_index_tmp;
  108.             }
  109.  
  110.             // Remove these options from the other people if the number of
  111.             // people with only these options is equal to the number of options
  112.             if (count($people_with_same_options) === $num_options) {
  113.                 foreach ($people as $p_index_tmp => $p_options_tmp) {
  114.                     if (array_search($p_index_tmp,$people_with_same_options) === false) {
  115.                         foreach (array_keys($p_options) as $option) {
  116.                             unset($people[$p_index_tmp][$option]);
  117.  
  118.                             $has_change = true;
  119.                         }
  120.                     }
  121.                 }
  122.             }
  123.         }
  124.     }
  125. }
  126. while ($has_change === true);
  127.  
  128. // Combine any remaining people into the result and sort it
  129. $results = $results + $people;
  130. ksort($results);
  131.  
  132. print_r($results);

这会产生以下结果：

  1. Array
  2. (
  3.     [0] => Array
  4.         (
  5.             [b] => 1
  6.         )
  7.  
  8.     [1] => Array
  9.         (
  10.             [r] => 1
  11.             [g] => 1
  12.         )
  13.  
  14.     [2] => Array
  15.         (
  16.             [r] => 1
  17.             [g] => 1
  18.         )
  19.  
  20.     [3] => Array
  21.         (
  22.             [r] => 1
  23.         )
  24.  
  25. )

例3：

此示例不适用于上述代码.假设有1个红球,1个绿球,1个蓝球,1个黄球和4个人.人1可以选择任何球,人2可以选择红色或绿色,人3可以选择绿色或蓝色,人4可以选择红色或蓝色.

在视觉上这看起来像：

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

由于红色,绿色和蓝色3种颜色是2,3和4人的唯一选择,因此它们完全包含在这3个人中,因此它们都可以从人1中消除,这意味着人1必须选择黄色.如果第一个人选择黄色的东西,那么其他人就不可能选择他们的球.

把它放到我的PHP程序中,我有这些输入值：

  1. // The quantity of each ball
  2. $balls = array(
  3.     'r' => 1,'y' => 1,'y'),);

但是我想不出如何循环查找这样的案例而不迭代每个可能的人组合.有什么想法可以做到这一点？

我更喜欢采用类似OOP的方法.所以我基本上从头开始.我希望你没关系.

所以,以下看起来(不可否认)非常丑陋,除了你的三个例子之外,我还没有测试过它,但是在这里：

  1. class Ball {
  2.     private $color;
  3.     public function __construct($color) {
  4.         $this->color = $color;
  5.     }
  6.     public function getColor() {
  7.         return $this->color;
  8.     }
  9. }
  10. class Ball_resource extends Ball {
  11.     private $num_available;
  12.  
  13.     public function __construct($color,$number) {
  14.         parent::__construct($color);
  15.         $this->num_available = $number;
  16.     }
  17.     public function take() {
  18.         $this->num_available--;
  19.     }
  20.  
  21.     public function isExhausted() {
  22.         return $this->num_available <= 0;
  23.     }
  24. }
  25. class Person {
  26.     /**
  27.      *
  28.      * @var Ball
  29.      */
  30.     private $allowed_balls = array();
  31.  
  32.     public function addConstraint($color) {
  33.         $this->allowed_balls[$color] = new Ball($color);
  34.         return $this;
  35.     }
  36.     public function getConstraints() {
  37.         return $this->allowed_balls;
  38.     }
  39.  
  40.     public function getNumberOfConstraints() {
  41.         return count($this->allowed_balls);
  42.     }
  43.  
  44.     /**
  45.      * return true if removal was successful; false otherwise
  46.      */
  47.     public function removeConstraint(Ball $ball) { // todo remove
  48.         if (isset ($this->allowed_balls [$ball->getColor()])) {
  49.             unset ($this->allowed_balls [$ball->getColor()]);
  50.             return true;
  51.         }
  52.         else {
  53.             // this means our puzzle isn't solvable
  54.             return false;
  55.         }
  56.     }
  57. }
  58. class Simplifier {
  59.     /**
  60.      *
  61.      * @var Person
  62.      */
  63.     private $persons = array ();
  64.     /**
  65.      *
  66.      * @var Ball_resource
  67.      */
  68.     private $availableBalls = array ();
  69.  
  70.     public function addPerson(Person $person) {
  71.         $this->persons[] = $person;
  72.         return $this;
  73.     }
  74.     public function addBallRessource(Ball_resource $ball_resource) {
  75.         $this->availableBalls[] = $ball_resource;
  76.         return $this;
  77.     }
  78.  
  79.  
  80.     public function getChoices() {      
  81.         $queue = $this->persons; // shallow copy
  82.  
  83.         while (count($queue) > 0) {
  84.             // find most constrained person(s)
  85.             $numberOfConstraints = 1; // each person must have at least one constraint
  86.             while (true) {
  87.                 $resolve_queue = array();
  88.                 foreach($queue as $person) {
  89.                     if ($person->getNumberOfConstraints() === $numberOfConstraints) {
  90.                         $resolve_queue[] = $person;
  91.                     }
  92.                 }
  93.                 // find mutually dependent constraint groups connected with a person
  94.                 $first_run = true;
  95.                 foreach ($resolve_queue as $startPerson) {
  96.                     // check if we havent already been removed via dependencies
  97.                     if ($first_run || !self::contains($queue,$startPerson)) {
  98.                         $dependent_persons = $this->findMutuallyDependentPersons($startPerson,$resolve_queue);
  99.                         // make a set out of their combined constraints
  100.                         $combinedConstraints = $this->getConstraintsSet($dependent_persons);
  101.                         $this->adjustResources($dependent_persons);
  102.                         $this->removeFromQueue($dependent_persons,$queue);
  103.                         // substract each ball of this set from all less constrained persons
  104.                         $this->substractConstraintsFromLessConstrainedPersons($queue,$combinedConstraints,$numberOfConstraints);
  105.                         $first_run = false;
  106.                         continue 3;
  107.                     }
  108.                 }
  109.                 $numberOfConstraints++;
  110.             }
  111.  
  112.         }
  113.         return $this->persons; // has been altered implicitly   
  114.     }
  115.  
  116.     private static function contains(array $haystack,Person $needle) {
  117.         foreach ($haystack as $person) {
  118.             if ($person === $needle) return true;
  119.         }
  120.         return false;
  121.     }
  122.  
  123.     private function findMutuallyDependentPersons(Person $startPerson,array $persons) {
  124.         // add recursion
  125.         $output = array();
  126.         //$output[] = $startPerson;
  127.         foreach($persons as $person) {
  128.             foreach ( $person->getConstraints () as $constraint ) {
  129.                 foreach ( $startPerson->getConstraints () as $targetConstraint ) {
  130.                     if ($constraint->getColor () === $targetConstraint->getColor ()) {
  131.                         $output [] = $person;
  132.                         continue 3;
  133.                     }
  134.                 }
  135.             }   
  136.         }
  137.         return $output;
  138.     }
  139.  
  140.     private function getConstraintsSet(array $persons) {
  141.         $output = array();
  142.         foreach ($persons as $person) {
  143.             foreach ($person->getConstraints() as $constraint) {
  144.                 foreach($output as $savedConstraint) {
  145.                     if ($savedConstraint->getColor() === $constraint->getColor()) continue 2;                   
  146.                 }
  147.                 $output[] = $constraint;
  148.             }
  149.         }
  150.         return $output;
  151.     }
  152.  
  153.     private function substractConstraintsFromLessConstrainedPersons(array $persons,array $constraints,$constraintThreshold) {
  154.         foreach ($persons as $person) {
  155.             if ($person->getNumberOfConstraints() > $constraintThreshold) {
  156.                 foreach($constraints as $constraint) {
  157.                     foreach($this->availableBalls as $availableBall) {
  158.                         if ($availableBall->isExhausted()) {
  159.                             $person->removeConstraint($constraint);
  160.                         }
  161.                     }                   
  162.                 }
  163.             }
  164.         }
  165.     }
  166.  
  167.     private function adjustResources(array $persons) {
  168.         foreach($persons as $person) {
  169.             foreach($person->getConstraints() as $constraint) {
  170.                 foreach($this->availableBalls as &$availableBall) {
  171.                     if ($availableBall->getColor() === $constraint->getColor()) {
  172.                         $availableBall->take();
  173.                     }
  174.                 }
  175.             }
  176.         }
  177.     }
  178.  
  179.     private function removeFromQueue(array $persons,array &$queue) {       
  180.         foreach ($persons as $person) {
  181.             foreach ($queue as $key => &$availablePerson) {
  182.                 if ($availablePerson === $person) {
  183.                     unset($queue[$key]);
  184.                 }
  185.             }
  186.         }
  187.     }
  188. }

整个事情被称为这样：

  1. // Example 2
  2. {
  3.     $person1 = new Person();
  4.     $person1->addConstraint("R")->addConstraint("R")->addConstraint("G")->addConstraint("B")->addConstraint("B")->addConstraint("B")->addConstraint("B");
  5.     $person2 = new Person();
  6.     $person2->addConstraint("R")->addConstraint("R")->addConstraint("G");
  7.     $person3 = new Person();
  8.     $person3->addConstraint("R")->addConstraint("R")->addConstraint("G");
  9.     $person4 = new Person();
  10.     $person4->addConstraint("R")->addConstraint("R");
  11.  
  12.     $redBalls = new Ball_resource("R",2);
  13.     $greenBalls = new Ball_resource("G",1);
  14.     $blueBalls = new Ball_resource("B",4);
  15.  
  16.     $simplifier = new Simplifier();
  17.     $simplifier->addPerson($person1)->addPerson($person2)->addPerson($person3)->addPerson($person4);
  18.     $simplifier->addBallRessource($redBalls)->addBallRessource($greenBalls)->addBallRessource($blueBalls);
  19.     $output = $simplifier->getChoices();
  20.  
  21.     print_r($output);
  22. }

同样对于例3：

  1. // Example 3
  2. {
  3.     $person1 = new Person();
  4.     $person1->addConstraint("R")->addConstraint("G")->addConstraint("B")->addConstraint("Y");
  5.     $person2 = new Person();
  6.     $person2->addConstraint("R")->addConstraint("G");
  7.     $person3 = new Person();
  8.     $person3->addConstraint("G")->addConstraint("B");
  9.     $person4 = new Person();
  10.     $person4->addConstraint("R")->addConstraint("B");
  11.  
  12.     $redBalls = new Ball_resource("R",1);
  13.     $greenBalls = new Ball_resource("G",1);
  14.     $yellowBalls = new Ball_resource("Y",1);   
  15.  
  16.     $simplifier = new Simplifier();
  17.     $simplifier->addPerson($person1)->addPerson($person2)->addPerson($person3)->addPerson($person4);
  18.     $simplifier->addBallRessource($redBalls)->addBallRessource($greenBalls)->addBallRessource($blueBalls)->addBallRessource($yellowBalls);
  19.     $output = $simplifier->getChoices();
  20.  
  21.     print_r($output);
  22. }

为简洁起见,我省略了原始输出.但是对于第二个例子,它基本上等于你在问题中的最后一个列表,而对于例3,它产生相当于：

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

猜你在找的PHP相关文章

Hessian通讯协议【附PHP源代码】
Hessian开源的远程通讯，采用二进制 RPC的协议，基于 HTTP 传输。可以实现PHP调用Java,Pyt...
初识Mongodb总结
初识Mongodb的一些总结,在Mac Os X下真实搭建mongodb环境,以及分享个Mongodb管理工具,学习...
初识Mongodb之[CURD]-PHP版
边看边操作,这样才能记得牢,实践是检验真理的唯一标准.光看不练假把式,光练不看傻把式,边看...
php学习日志 - echo&print
在php中，结果输出一共有两种方式：echo和print，下面将对两种方式做一个比较。 echo与pri...
The mbstring extension is missing. Please check your PHP configuration错误及解决方法
在安装好wampServer后，一直没有使用phpMyAdmin,今天用了一下，phpMyAdmin显示错误：The m...
解决Windows Live Writer错误:WindowsLive.Writer.CoreServices.HttpRequestHelper的类型初始值设定发生异常
以前用Windows Live Writer写日志都好好的，前几天用写完日志，点击发布，突然弹出意外错误...
在PHP项目中使用Standford Moss代码查重系统
Standford Moss 系统是斯坦福大学大名鼎鼎的代码查重系统，它可以查出哪些同学提交的代码是...
Windows下PHP安全环境的搭建
笔者一直在Windows环境下搭建PHP的运行环境，大大小小的运行环境用过不少，从开始的WAMP到...
ThinkPHP5作业管理系统中处理学生未交作业与已交作业信息
在作业管理系统中，学生登陆到个人中心后可以通过左侧的菜单查看自己已经提交的作业和未提...
ThinkPHP5项目目录规划实践
ThinkPHP5安装后（或者下载后的压缩文件解压后）可以看到下面的目录结构： 一般的信息管理...
PHPJavaJava SEPythonC#C&C++RubyVBasp.NetGoPerlnettyDjangoDelphiJsp.NET CoreSpringFlaskSpringbootSpringMVCLuaLaravelMybatisAspGroovyThinkPHPYiiswoole
文件时间pythonm相等性PHP Warning时间问题问题解决pcntl_signal采样点wav模块动态文本调用频率限制对外暴露多个访问请求更新数据表模型结构type()方法比较速度手写体sobel算子保存模型Image类nn.Conv2dpytorch1.0kaggleDCGAN交并比range()用法打印模型反卷积卷积