Tell me which way to think. It is necessary to come up with a table filling algorithm. It is necessary to fill in the necessary cells, so that in each row (B) k cells were filled, in each column (N) r cells were filled and that each random pair of cells was found in two (s) rows. All that is, this, the fact that the conditions are always met:

  • Bk = Nr
  • r (k-1) = L (N-1)
  • B> = N
  • r> = k

I tried it just manually, with different shifts, but after 3-4 lines of confusion. Here is an example of the result. Result example
(source: joxi.ru )

  • Uh ... And what does it mean "that each random pair of cells be repeated to occur in two (L) lines"? What is "every random pair of cells"? - VladD
  • @VladD that is, each pair of different cells must be in two lines. For example, the first row contains the 1st and 3rd cells and the second row also. That is, each pair is repeated exactly 2 times. - Alexey Kleandrov
  • @VladD here is an example of what should happen. Example - Alexey Kleandrov
  • The picture is not loaded. Each pair of cells lies exactly in one place. Or do you mean the values recorded in the cells? - VladD
  • @VladD Initially, in all values ​​of 0, to fill in means to put 1. For each pair it means that if the first line in the first and third column is 1, then in any other line there must be one. That is, the pair, as you correctly corrected, the values ​​will be repeated. Analogy: the tournament table, in each round a fixed number of teams, each team plays a fixed number of rounds, each pair of teams occurs exactly in 2 rounds. - Alexey Kleandrov

1 answer 1

1. Chess analogy

Sports analogy in this case is more than appropriate. The case in the picture is completely similar to the game of chess in the Swiss system B = 15 participants in k / 2 = 2 rounds in two colors for N = 10 game days (one round per day) on r / 2 = 3 boards. Additional condition: each participant plays no more than one tour per day. Accordingly, we will approach this issue.

2. Pairs of networks

For each network s, we create an array of B - 1 other networks and start a decreasing counter of pairs c = k / 2 . When a pair of networks is formed, then another network should be removed from their arrays, and the pair counters should be reduced by one. When resetting the counter, reset the corresponding array.

All possible sets of pairs for the first network are combinations of B - 1 elements of its k / 2 array. For subsequent networks, the question is determined by their arrays and pairs counters.

3. Linking pairs of networks to nodes

For each pair of consecutive nodes we create an array of B networks and a decreasing counter c1 = r / 2 . After binding a pair of networks to a pair of nodes, we cross out each node from the array and reduce the counter. When resetting the counter, reset the corresponding array.

Parallel with the binding we are filling the table. At the end of the binding, the table will be filled as required.