I have a set of N^2 numbers and N bins. Each bin is supposed to have N numbers from the set assigned to it. The problem I am facing is finding a set of distributions that map the numbers to the bins, satisfying the constraint, that each pair of numbers can share the same bin only once.
A distribution can nicely be represented by an NxN matrix, in which each row represents a bin. Then the problem is finding a set of permutations of the matrix' elements, in which each pair of numbers shares the same row only once. It's irrelevant which row it is, only that two numbers were both assigned to the same one.
Example set of 3 permutations satisfying the constraint for N=8:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
0 8 16 24 32 40 48 56 1 9 17 25 33 41 49 57 2 10 18 26 34 42 50 58 3 11 19 27 35 43 51 59 4 12 20 28 36 44 52 60 5 13 21 29 37 45 53 61 6 14 22 30 38 46 54 62 7 15 23 31 39 47 55 63
0 9 18 27 36 45 54 63 1 10 19 28 37 46 55 56 2 11 20 29 38 47 48 57 3 12 21 30 39 40 49 58 4 13 22 31 32 41 50 59 5 14 23 24 33 42 51 60 6 15 16 25 34 43 52 61 7 8 17 26 35 44 53 62
A permutation that doesn't belong in the above set:
0 10 20 30 32 42 52 62 1 11 21 31 33 43 53 63 2 12 22 24 34 44 54 56 3 13 23 25 35 45 55 57 4 14 16 26 36 46 48 58 5 15 17 27 37 47 49 59 6 8 18 28 38 40 50 60 7 9 19 29 39 41 51 61
Because of multiple collisions with the second permutation, since, for example they're both pairing the numbers 0 and 32 in one row.
Enumerating three is easy, it consists of 1 arbitrary permutation, its transposition and a matrix where the rows are made of the previous matrix' diagonals.
I can't find a way to produce a set consisting of more though. It seems to be either a very complex problem, or a simple problem with an unobvious solution. Either way I'd be thankful if somebody had any ideas how to solve it in reasonable time for the N=8 case, or identified the proper, academic name of the problem, so I could google for it.
In case you were wondering what is it useful for, I'm looking for a scheduling algorithm for a crossbar switch with 8 buffers, which serves traffic to 64 destinations. This part of the scheduling algorithm is input traffic agnostic, and switches cyclically between a number of hardwired destination-buffer mappings. The goal is to have each pair of destination addresses compete for the same buffer only once in the cycling period, and to maximize that period's length. In other words, so that each pair of addresses was competing for the same buffer as seldom as possible.
EDIT:
Here's some code I have. CODE
It's greedy, it usually terminates after finding the third permutation. But there should exist a set of at least N permutations satisfying the problem.
The alternative would require that choosing permutation I involved looking for permutations (I+1..N), to check if permutation I is part of the solution consisting of the maximal number of permutations. That'd require enumerating all permutations to check at each step, which is prohibitively expensive.
I’m having trouble understanding your constraint “each pair of numbers can share the same bin only once”. Isn’t that trivially true of any arrangement of N^2 unique numbers? Can you show an arrangement that fails the constraint?
– Jim Lewis21 августа 2009, 23:24If you still like your code in the morning :-), post it as an answer so we can upvote you some more! This was a really interesting problem!
– Jim Lewis22 августа 2009, 05:24P (a, b, i) может быть выражено как «R (a, i) == R (b, i)», где R - функция, сопоставляющая пару (a, i) с количеством строка, в которой элемент a появляется в перестановке i.
– Steve Jessop21 августа 2009, 23:38Формально, пусть P (a, b, i) будет предикатом «a и b появляются в одной строке в перестановке i», и предположим, что имеется n перестановок. Тогда ограничение таково: «не существует a, b <= N ^ 2 и i, j <= n таких, что P (a, b, i) && P (a, b, j)».
– Steve Jessop21 августа 2009, 23:36Ограничение должно выполняться для всего набора перестановок. Таким образом, если одна перестановка помещает числа 1 и 2 в одну строку, никакая другая перестановка в наборе больше не может помещать 1 и 2 в одну строку.
– 21 августа 2009, 23:27Весь вопрос многословен. Непонятно, что вы подразумеваете под парой. Что вы имеете в виду под «ограничением, согласно которому каждая пара чисел может использовать одну и ту же ячейку только один раз»?
– Alex21 августа 2009, 23:24