示例1：
在一个简单的情况下，假设我们有两个人，一个红球和一个绿球。第一个人可以选择任何一个球，但第二个人只能选择绿色的球。可以用以下方式表示：
Person 1: RG
Person 2: G
由于我们知道第二个人必须选择绿色球，这意味着第一个人不能选择那个球，因此必须选择红色球。所以可以简化为：
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
由于第四个人只有一种选项，我们知道他必须选择红球。因此，我们可以从其他所有人中消除一个红球：
Person 1: RGBBBB
Person 2: RG
Person 3: RG
Person 4: RR
然而这就是问题所在。我们可以看到，第二个人和第三个人必须选择一个红色球和一个绿色球，我们只是不知道哪个人会选择哪个颜色的球。但由于我们只剩下一个红球和一个绿球，所以红色和绿色也可以从第一个人的选择中排除掉：
Person 1: BBBB
Person 2: RG
Person 3: RG
Person 4: RR
现在，我们可以从每个条目中删除重复项，以得到以下选项：
Person 1: B
Person 2: RG
Person 3: RG
Person 4: R
我们知道第一和第四个人的选择，而第二和第三个人在红色和绿色之间做出选择。
为了解决这个问题，我会循环遍历每个人，首先如果某个人只有一种球类型，就把这个人从数组中删除并将其放入结果数组中（因为我知道这个人必须选择这种类型的球），然后从数组中的其他人那里删除一个相同类型的球（如果有的话）。
完成这些操作后，我认为规则是：
如果有$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);
This produces 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 this would look like:
Person 1: RGBY
Person 2: RG
Person 3: GB
Person 4: RB
Since the 3 colors red, green and blue are the only options for persons 2, 3 and 4, they are completely contained within these 3 people and they can therefore can all be eliminated from person 1, meaning person 1 must choose yellow. If person 1 were to choose anything but yellow, it would be impossible for the other people to choose their balls.
Putting 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 can't think of how to loop through to find cases like this without iterating through every single possible combination of people. Any ideas how this could be done?