javascript - Spot it 算法 - js

Question

在游戏 Dobble ("Spot it") 中，有一副 57 张纸牌，每张纸牌上有 8 个不同的符号。该系统是随机选择的任意两张牌将只有一个匹配的符号。这促使我了解系统背后的数学背景，因此我编写了一个简单的算法:

let getCards = function(symbolCount) {
  let n = symbolCount - 1,
    cards = [],
    card = []
  for (i = 0; i < n + 1; i++)
    card.push(i)
  cards.push(card)
  for (j = 1; j <= n; j++) {
    let card = [1]
    for (k = 1; k <= n; k++)
      card.push(n + n * (j - 1) + k)
    cards.push(card)
  }
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      let card = [i]
      for (k = 1; k <= n; k++)
        card.push(n + 1 + n * (k - 1) + (((i - 1) * (k - 1) + j - 1) % n))
      cards.push(card)
    };
  return cards;
}

let pack = getCards(8).join("\n").split(",").join(", ");
console.log(pack)

该算法到目前为止已经运行了几天，但今天我提到了一个错误(可能发生的最糟糕的错误):两张牌上有两个相同的对。

0, 1, 2, 3, 4, 5, 6, 7
1, 8, 9, 10, 11, 12, 13, 14
1, 15, 16, 17, 18, 19, 20, 21
1, 22, 23, 24, 25, 26, 27, 28
1, 29, 30, 31, 32, 33, 34, 35       This one ("1", "35")
1, 36, 37, 38, 39, 40, 41, 42
1, 43, 44, 45, 46, 47, 48, 49
1, 50, 51, 52, 53, 54, 55, 56
1, 8, 15, 22, 29, 36, 43, 50
1, 9, 16, 23, 30, 37, 44, 51
1, 10, 17, 24, 31, 38, 45, 52
1, 11, 18, 25, 32, 39, 46, 53
1, 12, 19, 26, 33, 40, 47, 54
1, 13, 20, 27, 34, 41, 48, 55
1, 14, 21, 28, 35, 42, 49, 56       This one ("1", "35")
...

---

我真的不知道错误发生在哪里，我必须提到我花了几个小时来寻找错误。因此，我们将不胜感激任何帮助。

Answer 1

(当我正在处理这个问题时，Damien Prot 发布了解释链接。无论如何我都会发布我的答案，有人可能会觉得它有帮助，并且最好有一个不依赖于外部链接的答案.)

如果我们从第一张有 8 个符号的牌开始，我们可以给它们编号:

0, 1, 2, 3, 4, 5, 6, 7

所有其他卡片都需要有一个与第一张卡片相同的符号，因此它们将分为八类:

0, x, x, x, x, x, x, x  
1, x, x, x, x, x, x, x  
2, x, x, x, x, x, x, x  
3, x, x, x, x, x, x, x  
4, x, x, x, x, x, x, x  
5, x, x, x, x, x, x, x  
6, x, x, x, x, x, x, x  
7, x, x, x, x, x, x, x  

让我们看看符号为 0 的卡片。它们不能与第一张卡片共享多个符号，因此它们不能有符号 1 到 7。它们也不能彼此共享任何其他符号，因为它们已经共享符号0. 这意味着每张卡片添加 7 个新符号:

0, 8, 9,10,11,12,13,14
0,15,16,17,18,19,20,21
0,22,23,24,25,26,27,28
0,29,30,31,32,33,34,35
0,36,37,38,39,40,41,42
0,43,44,45,46,47,48,49
0,50,51,52,53,54,55,56

每个类别中的最大卡片数量为 7。如果有第八张卡片:

1,57,58,59,60,61,62,63  

我们在为其他类别的卡片选择符号时会遇到麻烦；他们将有一个符号 1 到 7，并与类别 0 中的每张卡片共享一个符号(但不是符号 0，因为它们将与第一张卡片共享两个符号)。所以他们只能与其他类别的 7 张牌共享一个符号。

类别 1 中的卡片如下所示:

1, 8,15,22,29,36,43,50
1, 9,16,23,30,37,44,51
1,10,17,24,31,38,45,52
1,11,18,25,32,39,46,53
1,12,19,26,33,40,47,54
1,13,20,27,34,41,48,55
1,14,21,28,35,42,49,56

每张牌都有符号 1，然后是类别 0 中每张牌的一个符号(但不是符号 0)；实际上，这意味着类别 0 的列被转换为类别 1 的行。类别 2 中的卡片类似:

2, 8,16,24,32,40,48,56
2, 9,17,25,33,41,49,50
2,10,18,26,34,42,43,51
2,11,19,27,35,36,44,52
2,12,20,28,29,37,45,53
2,13,21,22,30,38,46,54
2,14,15,23,31,39,47,55

您会注意到，与类别 1 相比，最后 6 列中的符号发生了旋转:第三列向上移动了 1 个位置，第四列向上移动了 2 个位置，第五列向上移动了 3 个位置，依此类推.从类别 2 到类别 3 时也是如此:

3, 8,17,26,35,37,46,55
3, 9,18,27,29,38,47,56
3,10,19,28,30,39,48,50
3,11,20,22,31,40,49,51
3,12,21,23,32,41,43,52
3,13,12,24,33,42,44,53
3,14,16,25,34,36,45,54

我们可以继续为其他类别这样做:

4, 8,18,28,31,41,44,54
4, 9,19,22,32,42,45,55
4,10,20,23,33,36,46,56
4,11,21,24,34,37,47,50
4,12,15,25,35,38,48,51
4,13,16,26,29,39,49,52
4,14,17,27,30,40,43,53

5, 8,19,23,34,38,49,53
5, 9,20,24,35,39,43,54
5,10,21,25,29,40,44,55
5,11,15,26,30,41,45,56
5,12,16,27,31,42,46,50
5,13,17,28,32,36,47,51
5,14,18,22,33,37,48,52

6, 8,20,25,30,42,47,52
6, 9,21,26,31,36,48,53
6,10,15,27,32,37,49,54
6,11,16,28,33,38,43,55
6,12,17,22,34,39,44,56
6,13,18,23,35,40,45,50
6,14,19,24,29,41,46,51

7, 8,21,27,33,39,45,51
7, 9,15,28,34,40,46,52
7,10,16,22,35,41,47,53
7,11,17,23,29,42,48,54
7,12,18,24,30,36,49,55
7,13,19,25,31,37,43,56
7,14,20,26,32,38,44,50

所以当使用每张卡片上有 8 个符号的卡片时，我们总共可以制作 57 张卡片:第一张卡片，加上 8 个类别的 8 − 1 = 7 张卡片。

一般来说，使用 N 个符号，我们最多可以制作 N × (N − 1) + 1 张牌。但是，这仅在 N 是质数加一时有效(因为否则旋转列不会创建唯一排列)。

(根据 Damien 的回答中链接的文章，当 N 是质数的幂加一(例如 3² + 1 = 10 ), 但这需要不同的方法，或者少于 N × (N − 1) + 1 张卡片。)

function DobbleCards(n) { // n-1 must be prime
    var cards = [];

    // first card and first category
    for (var crd = 0; crd < n; crd++) {
        var symbols = [0];
        for (var sym = 1; sym < n; sym++) {
            symbols.push(crd * (n-1) + sym);
        }
        cards.push(symbols.slice());
    }

    // other categories
    for (var cat = 1; cat < n; cat++) {
        for (var crd = 0; crd < n-1; crd++) {
            var symbols = [cat];
            for (var sym = 1; sym < n; sym++) {
                symbols.push(1 + sym * (n-1) + ((cat-1) * (sym-1) + crd) % (n-1));
            }
            cards.push(symbols.slice());
        }
    }
    return cards;
}

var deck = DobbleCards(8);
for (var i in deck) {
    document.write(deck[i] + "<br>");
}