My question concerns combinations and, more specifically, mutations between different combinations. It was inspired by the game of Dobble.
In the game Dobble, there are (or should be) 57 cards each showing 8 images from a set of 57 images. This means that for any two cards, there is one and only one image which is common to both cards.
In a general case, you can create a set of cards with n images per card, and a total of n * (n - 1) + 1 images (and the same number of cards).
Each image will appear on n cards, along with (n - 1) other images on each card, giving a total of n * (n - 1) other images, plus the given image, resulting in a total of n * (n - 1) + 1. Since each image appears n times, and there n images per card, there must also be n * (n - 1) + 1 cards.
So, the 8 images per card in Dobble lead to 8 * 7 + 1 = 57 images and cards.
A general solution for n images per card with m images in common between any two cards is only possible for certain values of m and n. Specifically, m has to be a factor of n * (n - 1) and the number of images (and cards) required is 1 + (n * (n - 1) / m).
There are cases where different values of m and n require the same number of images and cards. This suggests that there may be optimal ways of mapping two such sets of cards to each other, and it is the optimization of this mapping that I would like to explore.
Examples: 5 images per card, 2 common images on each card requires 11 images (labelled here in hexadecimal, for simplicity):
12345
12 678
1 3 6 9A
1 4 7 9 B
1 5 8 AB
23 89 B
2 4 6 AB
2 5 7 9A
34 78 A
3 567 B
456 89
6 images per card, 3 common images per card also requires 11 images:
123456
123 789
1 34 7 AB
1 45 89 B
1 5678 A
12 6 9AB
23 5 8 AB
2 45 7 9A
2 4 678 B
34 6 89A
3 567 9 B
The optimal mapping, if it exists, would require no more than 11 changes, all of which are additions. Using brute force, I have found a solution that requires 19 changes, with 8 alterations as well as 11 additions.
5 images 6 images Change
1) 12345 => 123456 +6
2) 12 678 => 1 5678 A 2 > 5 +A
3) 1 3 6 9A => 12 6 9AB 3 > 2 +B
4) 1 4 7 9 B => 1 34 7 AB 9 > A +3
5) 1 5 8 AB => 23 5 8 AB 1 > 2 +3
6) 23 89 B => 123 789 B > 7 +1
7) 2 4 6 AB => 2 4 678 B B > 8 +7
8) 2 5 7 9A => 2 45 7 9A +4
9) 34 78 A => 34 6 89A 7 > 6 +9
A) 3 567 B => 3 567 9 B +9
B) 456 89 => 1 45 89 B 6 > 1 +B
My brute force approach assumes that the numbers in one set correspond to the same image as the numbers in the other set. Since this is not necessarily true, it may be possible to find a more compact solution.
I would be interested to learn what formal studies have been done in this area ... and what practical applications this might have.
