PHP求助：如何基于约束数组生成colors与boxes的唯一组合

Hey there! Let's break down how to solve this unique pairing problem in PHP step by step. First, let's align on the goal: we need to match each color in $colors to exactly one box in $boxes, with every pair allowed by $possible_combos, and no box reused across colors.

First, Clarify the Constraint Structure #

Let's assume your $possible_combos is an array of allowed (color, box) pairs—this is the most common setup for this kind of problem. For example:

$colors = ['red','blue','green','yellow'];
$boxes = ['circular','squared','hexagonal','triangular'];
$possible_combos = [
    ['red', 'circular'],
    ['red', 'squared'],
    ['blue', 'hexagonal'],
    ['green', 'triangular'],
    ['green', 'circular'],
    ['yellow', 'squared'],
    ['yellow', 'triangular'],
];

If your constraint is structured differently (like a nested array where keys are colors and values are allowed boxes), we can adjust the code easily.

Approach 1: Backtracking (Perfect for Small Datasets) #

Since your arrays are small (4 elements each), a backtracking approach is simple and effective. We'll recursively test valid pairs, keeping track of used boxes to ensure uniqueness.

Here's a working implementation:

function findValidCombination($colors, $boxes, $possible_combos, $usedBoxes = [], $currentPairings = []) {
    // Base case: we've paired all colors successfully
    if (count($currentPairings) === count($colors)) {
        return $currentPairings;
    }

    // Grab the next color we need to pair
    $currentColor = $colors[count($currentPairings)];

    // Loop through all allowed pairs for this color
    foreach ($possible_combos as $combo) {
        list($color, $box) = $combo;
        // Check if this pair is for our current color and the box isn't used yet
        if ($color === $currentColor && !in_array($box, $usedBoxes)) {
            // Mark the box as used and add the pairing to our current set
            $newUsedBoxes = $usedBoxes;
            $newUsedBoxes[] = $box;
            $newPairings = $currentPairings;
            $newPairings[$color] = $box;

            // Recurse to pair the next color
            $result = findValidCombination($colors, $boxes, $possible_combos, $newUsedBoxes, $newPairings);
            if ($result !== null) {
                return $result; // Return the first valid combination we find
            }
        }
    }

    // No valid path from this point—backtrack
    return null;
}

// Run the function and output results
$validCombination = findValidCombination($colors, $boxes, $possible_combos);

if ($validCombination) {
    echo "Valid unique combination:\n";
    print_r($validCombination);
} else {
    echo "No valid unique combination exists with the given constraints.";
}

How This Works:

• We start with empty lists of used boxes and pairings.
• For each color in sequence, we test all allowed boxes that haven't been used yet.
• We recursively move to the next color, carrying forward our used boxes and current pairs.
• If we successfully pair all colors, we return the valid set. If a path hits a dead end (no available boxes for a color), we backtrack and try another option.

Approach 2: Hungarian Algorithm (Better for Larger Datasets) #

If your arrays grow beyond a small size, backtracking becomes inefficient. The Hungarian Algorithm is a classic solution for bipartite matching problems (which this is: colors on one side, boxes on the other, edges for allowed pairs).

Here's a simplified PHP implementation:

function hungarianAlgorithm($colorBoxMap) {
    $colors = array_keys($colorBoxMap);
    $boxes = array_unique(array_merge(...array_values($colorBoxMap)));
    $boxIndex = array_flip($boxes);
    $n = count($colors);
    $m = count($boxes);

    $u = array_fill(0, $n+1, 0);
    $v = array_fill(0, $m+1, 0);
    $p = array_fill(0, $m+1, 0);
    $way = array_fill(0, $m+1, 0);

    for ($i = 1; $i <= $n; $i++) {
        $p[0] = $i;
        $minv = array_fill(0, $m+1, INF);
        $used = array_fill(0, $m+1, false);
        $j0 = 0;
        do {
            $used[$j0] = true;
            $i0 = $p[$j0];
            $delta = INF;
            $j1 = 0;
            foreach ($colorBoxMap[$colors[$i0-1]] as $box) {
                $j = $boxIndex[$box] + 1;
                $cur = 1 - $minv[$j]; // Treat valid pairs as high-priority (cost = 1)
                if ($cur < $delta) {
                    $delta = $cur;
                    $j1 = $j;
                }
            }
            for ($j = 0; $j <= $m; $j++) {
                if ($used[$j]) {
                    $u[$i0] += $delta;
                    $v[$j] -= $delta;
                } else {
                    $minv[$j] -= $delta;
                }
            }
            $j0 = $j1;
        } while ($p[$j0] !== 0);

        do {
            $j1 = $way[$j0];
            $p[$j0] = $p[$j1];
            $j0 = $j1;
        } while ($j0 !== 0);
    }

    $result = [];
    for ($j = 1; $j <= $m; $j++) {
        if ($p[$j] !== 0) {
            $result[$colors[$p[$j]-1]] = $boxes[$j-1];
        }
    }

    // Filter to only include our original colors
    return array_intersect_key($result, array_flip($colors));
}

// Convert $possible_combos to a color => allowed boxes map first
$colorBoxMap = [];
foreach ($possible_combos as $combo) {
    list($color, $box) = $combo;
    if (!isset($colorBoxMap[$color])) {
        $colorBoxMap[$color] = [];
    }
    $colorBoxMap[$color][] = $box;
}

// Run the algorithm and output results
$validCombination = hungarianAlgorithm($colorBoxMap);

if (count($validCombination) === count($colors)) {
    echo "Valid unique combination:\n";
    print_r($validCombination);
} else {
    echo "No valid unique combination exists with the given constraints.";
}

How This Works:

• We first convert $possible_combos into a map where each color points to its allowed boxes.
• The algorithm finds the maximum matching in the bipartite graph, ensuring each color is paired with exactly one unique box (and vice versa) if possible.

Key Notes: #

• If no valid combination exists (e.g., a color has no available boxes left after others are paired), both functions will signal this with a null or incomplete array.
• If you need all possible valid combinations instead of just one, modify the backtracking function to collect all results instead of returning the first match.

内容的提问来源于stack exchange，提问作者Harris Qureshi