Spot it算法-js [英] Spot it algorithm - js

问题描述

在游戏Dobble("Spot it")中，有一包57张纸牌，每张纸牌上都有8个不同的符号.系统是，随机选择的任何两张牌都只会有一个匹配符号.这激发了我了解系统背后的数学背景，所以我写了一个简单的算法:

In the game Dobble ("Spot it") , there is a pack of 57 playing cards, each with 8 different symbols on them. The system is that any two cards chosen at random will have just one matching symbol. This spurred me on to the mathematical background behind the system and so I wrote an simple algorithm:

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)

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

The algorithm is working so far for a few days but today I mentioned a bug ( The worst one that could have occurred ): There are two identical pairs on two cards.

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")
...

---

我真的不知道该错误发生在哪里，我必须提到我已经花费了数小时来查找该错误.因此，我们将不胜感激任何帮助.

---

I really get no idea where the bug occurres and I must mention that I've spent hours in finding the bug. So any help would be really appreciated.

推荐答案

(在我从事此工作的同时，Damien Prot发布了指向说明的链接.无论如何，我都会发布答案，有人可能会发现它很有帮助，并且最好有一个不依赖外部链接的答案.)

如果我们从带有8个符号的第一张卡片开始，就可以对它们进行编号:

If we start off with the first card with 8 symbols, we can number them:

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

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

All other cards need to have one symbol in common with the first card, so they will fall into eight categories:

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个新符号:

Let's look at the cards which have symbol 0. They cannot share more than one symbol with the first card, so they cannot have symbols 1 to 7. They also cannot share any additional symbols with each other, because they already share symbol 0. This means each card adds 7 new symbols:

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.如果有第八张纸牌:

The maximum number of cards in each category is 7. If there were an eighth card:

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

在其他类别的卡片中选择符号时会遇到麻烦；它们将具有1到7的符号，并与类别0中的每个卡共享一个符号(但不包含符号0，因为这样它们将与第一张卡共享两个符号).因此，他们只能与其他类别的7张卡片共享一个符号.

we would run into trouble when choosing the symbols for the cards in the other categories; they would have a symbol 1 to 7, and share a symbol with each of the cards in category 0 (but not symbol 0, because then they'd share two symbols with the first card). So they can share a symbol with only 7 cards in the other categories.

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

The cards in category 1 look like this:

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中的卡片类似:

Each card has symbol 1, and then a symbol from each of the cards in category 0 (but not symbol 0); practically, this means that the columns from category 0 are transformed into rows for category 1. The cards in category 2 are similar:

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:

You'll notice that the symbols in the last 6 column are rotated when compared to category 1: the third column up by 1 position, the fourth column up by 2 positions, the fifth column up by 3 positions, and so on. The same is done when going from category 2 to category 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

我们可以继续对其他类别执行此操作:

And we can continue doing this for the other categories:

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张卡.

So when using cards with 8 symbols on each card, we can make a total of 57 cards: the first card, plus 8 categories of 8 − 1 = 7 cards.

通常，使用N个符号，我们最多可以将N次乘以N.(N负1)+ 1张牌.但是，这仅在N为素数加1时有效(因为否则旋转列将不会创建唯一的排列).

In general, with N symbols, we can make a maximum of N × (N − 1) + 1 cards. However, this works only when N is a prime number plus one (because otherwise rotating the columns doesn't create unique permutations).

(根据Damien答案中链接的文章，当N是素数加1的幂时(例如3 ² + 1 = 10)，但是那需要一种不同的方法，或者少于N×(N− 1)+ 1卡.)

(According to the article linked in Damien's answer, it is also possible to create a Dobble deck when N is a power of a prime plus one (e.g. 3² + 1 = 10), but that would need a different method, or have fewer than N × (N − 1) + 1 cards.)

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

这篇关于Spot it算法-js的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！