title: Finding a set of permutations, with a constraint
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>Example set of 3 permutations satisfying the constraint for N=8:</p>
  
  <pre>
   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
  </pre>
  
  <pre>
   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
  </pre>
  
  <pre>
   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
  </pre>
  
  <p>A permutation that doesn't belong in the above set:</p>
  
  <pre>
   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
  </pre>
  
  <p>Because of multiple collisions with the second permutation, since, for example they're both pairing the numbers 0 and 32 in one row.</p>
  
  <hr>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <hr>
  
  <p>EDIT:</p>
  
  <p>Here's some code I have.
  <a href="http://www.pastey.net/122630" rel="nofollow noreferrer">CODE</a></p>
  
  <p>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.</p>
  
  <p>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.</p>