消除不可能的选择

Question

我试图以编程方式解决这个问题时遇到了一些麻烦.这不是我正在做的事情,但为了简化事情,我们说有一定数量的球和一定数量的人.每个人必须选择一个球,人们可能只限于他们可以选择的球类型.目标是确定人们在消除所有不可能的组合后必须选择哪些选项.

例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个蓝球,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,
    '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'),
);

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

Answer 1

我最终决定做的是半蛮力，但是我对其进行了调整，以便它不必遍历每个组合，因此在大多数情况下，迭代次数应该比每个可能的组合少得多。

组合总数等于exp(2,count(balls))（即 2^{球类型}），因此如果我们有 20 种球，那么如果我们要检查每一种球，则必须检查 1048576 种不同的球组合。不仅迭代次数太多，实际上我之前就已经用完了内存，只有 16 个球的颜色。

要获得每种可能的组合，您可以使用此函数（源代码）：

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

但是，如果我们回到原来的规则：

如果有 $n 人都具有相同的 $n 个选项（或其子集），则可以从所有其他人中删除这些选项，其中 $n 小于总人数。

正如我们所看到的，如果我们已经超出了$n选项数量，我们可以跳过任何未来的迭代。请注意，当我们有多个相同颜色的球时，在此函数中算作多个球。

一旦我们获得了不同的可能子集，我们就会循环遍历这些人，看看是否有$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 种总组合），但是我们只需要在函数中进行 6 次迭代getBallSubsets()，因此这比暴力破解每种可能的组合要高效得多。