CODEWITHSUNDEEP
algorithm
fl00r
fl00r

Reputation: 83680

Sets of size N with 1 item in common between each pair

For example I have following sets (N=4). Any two rows have got only 1 number in common:

1  2  3  4
2  5  6  7
3  5  8  9
4  6  8  10
1  5  10 11
2  9
...

Can anyone suggest an algorithm to generate such sequences? With minimal number of unique numbers (with more or less uniform distribution of those numbers).

In an hour I came with nothing. I even can't create this sequence long enough on the paper.

For example this won't work, because of wrong numbers distribution:

1  2  3  4
1  5  6  7
1  8  9  10
1  11 12 13
1  14 15 16
...

I've found out this sequence:

1 2 3 4
1 5 6 7
1 8 9 10
1 11 12 13
2 5 8 11
2 6 9 12
2 7 10 13
3 5 9 13
3 6 10 11
3 7 8 12
4 5 10 12
4 6 8 13
4 7 9 11

Upvotes: 2

Views: 188

Answers (2)

ludvik02
ludvik02

Reputation: 31

You need to generate points of so-called "Block design" (see Wikipedia). The most interesting solution is if N-1 is the prime number or its power. Then look at "Projective planes". For N=4, you need to generate projective plane of 3rd order. Both number of rows and number of symbols (numbers) needed is in this case N*N-N+1. So, for N=4, it is 13.

The way to generate projective planes is co-incidence matrix in Paige-Wexler normal form (See Paige L.J., Wexler Ch., A Canonical Form for Incidence Matrices of Projective Planes...., In Portugalie Mathematica, vol 12, fasc 3, 1953). Then for every row, you just write down column indexes where you see ones in the incidence matrix. For N=4 (order=3), the example of co-incidence matrix in Paige-Wexler normal form is in Wikipedia. For other prime orders, you will need to rotate rows of permutation matrices using the multiplication group of Galois field of corresponding order, which makes it a little bit tricky. It is even more tricky for non-prime orders (i.e. prime power orders, like 8 or 9).

The game of Dobble is an example of Projective plane of the 7th order. Dobble Kids is Projective plane of 5th order. Unfortunately, the game producer crippled the Projective plane by deliberately omitting to print 2 cards (or 1 card in case od Dobble Kids). Fortunately this game popularized Projective planes, so you will find ready made projective field generators as Dobble generators. For example:

https://math.stackexchange.com/questions/1303497/what-is-the-algorithm-to-generate-the-cards-in-the-game-dobble-known-as-spo

In all correct answers in this link, you will note that indeed all the generators are based on incidence matrix in Paige-Wexler normal form. Unfortunately, they work only for prime orders.

By the way, if you have Dobble(=SpotIt) game set you can replace symbols by numbers and this will give you 55 rows of 7th order projective plane. In order to get all 57 rows, the missing two cards are (at least in my set): (snowman, light bulb, dog, exclamation mark, ladybug, hammer, eye, skull) and (snowman, ice, cactus, human, question mark, flower, green dino, maple leaf).

Upvotes: 1

Thomas Baruchel
Thomas Baruchel

Reputation: 7517

I think your problem is related to something which is involved in a game called "Dobble". Have a look at the link: https://math.stackexchange.com/questions/464932/dobble-card-game-mathematical-background

Upvotes: 2

Related Questions