Finding a set of permutations, with a constraint

Asked
Viewd3825

8

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:24
  • If 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:24
  • P (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

4 ответов

4

Вам нужен комбинаторный блочный дизайн . Используя номенклатуру на связанной странице, вам нужны дизайны размера (n ^ 2, n, 1) для максимального k. Это даст вам n (n + 1) перестановок, используя вашу номенклатуру. Это максимум, теоретически возможный с помощью счетного аргумента (см. Объяснение в статье для получения b из v, k и лямбда). Такие схемы существуют для n = p ^ k для некоторого простого p и целого числа k с использованием аффинной плоскости. Предполагается, что единственные существующие аффинные плоскости имеют такой размер. Следовательно, если вы можете выбрать n, возможно, этого ответа будет достаточно.

Однако, если вместо максимально теоретически возможного количества перестановок вы просто хотите найти большое количество (максимальное, которое вы можете для данного n ^ 2), я не уверен, как называется изучение этих объектов.

  • Огромное спасибо! На странице википедии о блочных проектах я нашел ссылку на базу данных, содержащую интересующее меня решение (64, 8, 1).

    24 августа 2009, 18:00
1

Возможно, вы могли бы переформулировать свою проблему в теории графов. Например, вы начинаете с полного графа с N × N вершинами. На каждом шаге вы разбиваете граф на N N-клик, а затем удаляете все использованные ребра.

Для этого случая N = 8 K64 имеет 64 × 63/2 = 2016 ребер, а шестьдесят четыре партии K8 имеют 1792 ребра, поэтому ваша проблема может не быть невозможной: -)

  • That sounds correct! And insightful – because the clique finding problem is known to be NP-complete in general. What I suspect is that the first few iterations (while the NxN graph is still relatively dense) are probably easy to find by brute force, but as edges are removed, the cliques take longer and longer to find.

    Jim Lewis22 августа 2009, 04:50
  • Well, finding maximal cliques is NP-complete. I’m not sure about this problem. I think the cliques would be easy to find if they exist, since every vertex has to be a member of one, and you’re only interested in size N. The problem is that a greedy algorithm will probably pick the wrong cliques and be unable to find all N, assuming N exist (well, that’s my gut feeling anyway).

    John Fouhy22 августа 2009, 06:17
  • Да, по сути, я реализовал поиск всех 8 кликов. Это быстро при наличии 2 начальных перестановок (найдено 40320 8-клик) и выполнимо при наличии 1 начальной перестановки (найдено 16 миллионов 8-клик). Но проблема: 1. Перечисление всех допустимых перестановок, то есть наборов из 8 8-клик, составляет 40320 ^ 8 или (16 миллионов) ^ 8. 2. Количество 8-клик и возможных перестановок на следующем шаге зависит от выбора перестановки на этом шаге, жадность действительно не работает. Для полного поиска при поиске перестановки I необходимо оценить все последующие перестановки (I + 1..N): /

    22 августа 2009, 09:19
4

Make a 64 x 64 x 8 array: bool forbidden[i][j][k] which indicates whether the pair (i,j) has appeared in row k. Each time you use the pair (i, j) in the row k, you will set the associated value in this array to one. Note that you will only use the half of this array for which i

To construct a new permutation, start by trying the member 0, and verify that at least seven of forbidden[0][j][0] that are unset. If there are not seven left, increment and try again. Repeat to fill out the rest of the row. Repeat this whole process to fill the entire NxN permutation.

There are probably optimizations you should be able to come up with as you implement this, but this should do pretty well.

  • Жадный подход, подобный этому, дает лишь небольшое количество перестановок перед завершением. Это было первое, что я попробовал.

    22 августа 2009, 10:02
  • +1, но я думаю, что ограничение более сильное: если пара появилась в одной строке, они не могут появляться вместе в любой строке в другой перестановке. Так, может быть, «запрещенный» массив должен быть 64x64 без последнего измерения?

    Jim Lewis22 августа 2009, 00:04
0

Верно, жадный стиль не работает, потому что у вас заканчиваются цифры.

Легко понять, что не может быть больше 63 перестановок, пока вы не нарушите ограничение. 64-го числа вам нужно будет связать хотя бы одно из чисел с другим, с которым он уже был связан. Принцип голубятни.

На самом деле, если вы воспользуетесь таблицей запрещенных пар, которую я предложил ранее, вы обнаружите, что существует максимум только N + 1 = 9 возможных перестановок, прежде чем вы закончите. В таблице есть N ^ 2 x (N ^ 2-1) / 2 = 2016 неизбыточных ограничений, и каждая новая перестановка будет создавать N x (N выберите 2) = 28 новых пар. Таким образом, все пары будут использованы после 2016/28 = 9 перестановок. Похоже, понимание того, что существует так мало перестановок, является ключом к решению проблемы.

Вы можете создать список из N перестановок, пронумерованных n = 0 ... N-1 как

 A_ij = (i * N + j + j * n * N) mod N^2
 

, который генерирует новую перестановку, сдвигая столбцы в каждой перестановке. Верхняя строка n-й перестановки - это диагонали n-1-й перестановки. РЕДАКТИРОВАТЬ: Ой ... это работает только тогда, когда N является простым.

Это пропускает последнюю перестановку, которую можно получить, переставив матрицу:

 A_ij = j * N + i
 
  • You also get the N+1 upper limit by examining the N-1 neighbors of a given value, e.g. 1. Each of the remaining N^2-1 numbers can appear only once in a row with 1, meaning there are at most (N^2-1)/(N-1)=N+1 unique rows, hence matrices, containing 1.

    outis23 августа 2009, 17:52