高效计算套装数量的方法！在桌子上

Question

我正在编程游戏套装！其中包括在十二张牌的桌子中找到一组有效的三张牌。 每张卡都有四个特征的独特组合：
-形状（椭圆形、菱形、花生形）
- 阴影（全、条纹、空）
-颜色（红、蓝、绿）
-数字（一、二、三）
一组有效的卡片由三张卡片组成，其中所有三张卡片上的每个特征要么全部相同，要么全部不同。

示例：

说明：第一张卡片具有以下特征（形状：椭圆形，阴影：全色，颜色：绿色，数量：一个）
第二张卡片有（形状：椭圆形，颜色：全色，颜色：绿色，数量：两张）
第三张卡片有（形状：椭圆形，颜色：全色，颜色：绿色，数量：三）
在该集合中，形状、色调和颜色都相同，而数字都不同，这意味着该集合遵循相同或所有不同的约束。如果第一张卡片的形状是菱形，则不会遵守所有三张卡片上的所有形状必须相同或不同的约束，从而使其无效。

我想计算十二张牌的表中有效组合的数量。 现在，我通过生成所有可能的集合并一一验证它们来暴力破解解决方案。 如何提高盘点数量的效率？ 如果我进行递归搜索而不是迭代，会更快吗？

我发现可以改进的一种方法是仅生成两张牌的所有可能组合并预测第三张牌，然后我只需要验证第三张牌是否在表中。

Answer 1

你提出的想法似乎不错：

查看每对卡片，找出需要哪张卡片与它们组成一组，然后看看桌子上是否有该卡片。

共有 3*3*3*3=81 张卡片，因此您可以通过数字（0..80）来识别它们。 81 个条目的数组可以作为一组来快速识别您桌上是否有某张牌。

给定两张牌，您可以通过应用规则得出第三张牌。如果对于某个维度（特征），两张卡具有相同的值，则第三张卡也应该具有相同的该特征值。如果两张牌在该特征上不同，则第三张牌应该具有该特征的剩余可能性。

下面是一个简单的 JavaScript 实现，其中输入可以指定为由四个字母组成的字符串 - 每个特征的第一个字母（“O”代表“Ovale”，“G”代表绿色，...等）。所以“OFR1”是有一个红色填充椭圆形的卡片的名称。

const charMap = { "O": 0, "D": 27, "P": 54, // Shapes
                  "F": 0, "S":  9, "E": 18, // Shades
                  "R": 0, "B":  3, "G":  6, // Colors
                  "1": 0, "2":  1, "3":  2, // Numbers
                };

function cardNameToId(name) {   
    return charMap[name[0]] + charMap[name[1]] + 
           charMap[name[2]] + charMap[name[3]];
}

function findSets(cardNames) {
    // Convert the names to card ids:
    const cards = cardNames.map(cardNameToId);
    // Define the array-backed set for the cards
    const table = Array(81).fill(-1);
    for (let i = 0; i < cards.length; i++) {
        // Mark the card with the index in the input
        //    The index helps to get the card's string representation later
        table[cards[i]] = i; 
    }
    // The found sets will be added to this array:
    const sets = [];
    // Iterate all pairs of cards:
    for (let i = 0; i + 2 < cards.length; i++) {
        const a = cards[i];
        for (let j = i + 1; j + 1 < cards.length; j++) {
            const b = cards[j];
            // Calculate what the matching third card should be
            let third = 0;
            for (let div = 1; div < 81; div *= 3) {
                const valA = Math.floor(a/div) % 3;
                const valB = Math.floor(b/div) % 3;
                third += (valA == valB ? valA : 3 - valA - valB) * div;
            }
            const k = table[third]; // Do we have that winning card
            if (k > j) { // Avoid repetition, and require i < j < k
                sets.push([cardNames[i], cardNames[j], cardNames[k]]);
            }
        }
    }
    return sets;
}

// Demo 
const cards = ["OFR1", "OEB2", "PFB1", "DFR3", "PSG2", "PSR1", 
               "DFG2", "PEG3", "DSB2", "OSG1", "PFB3", "PSR3"];
const sets = findSets(cards);
console.log("Number of sets:", sets.length); // 5
console.log(sets); // the details of the found sets