Упорядочить элементы в матрице любого размера

Question

Это скорее обсуждение, чем вопрос как таковой, поскольку я мог бы решить это с помощью кода, но я думаю, что должны быть лучшие способы сделать это.

Мне нужно распределить элементы в матрице так, чтобы каждый квадрант матрицы (размеры которой не обязательно делимы на 4) содержит равное (или как можно более близкое) количество указанных элементов, но расположенное случайно в пределах этого квадранта. Остальная часть матрицы должна содержать случайные элементы другого типа.

Например, распределяя 10 элементов (А) в виде матрицы 9x6 может выглядеть следующим образом:

Который раскрывает проблему, что делать со средними линиями, когда измерение нечетное. Он может быть включен в один квадрант или другой случайным образом (тот факт, что нет как в 3 средних столбцах, просто шанс)

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

Я на полпути кодирования это в C#, идея в том, что-то вроде этого (он не работает, как еще и некоторые вещи, которые являются неэффективными, чтобы попытаться сделать код более читаемым):

private void PopulateQuadrants(ref Test5Target[,] matrix, 
     int xBeginQuadrant, int xEndQuadrant, int yBeginQuadrant, int yEndQuadrant, int targets) 
    { 
     if (targets == 0) 
     { 
      return; 
     } 
     else if (targets == 1) 
     { 
      Random rand = new Random(); 
      matrix[rand.Next(xBeginQuadrant, xEndQuadrant), rand.Next(yBeginQuadrant, yEndQuadrant)] 
       = new Test5Target(ChosenTarget, UseAdvancedTargets); 
      for (int x = xBeginQuadrant; x < xEndQuadrant; x++) 
      { 
       for (int y = xBeginQuadrant; y < xEndQuadrant; y++) 
       { 
        if (matrix[x, y] == null) 
        { 
         int type = rand.Next(TargetCount); 
         while(type == ChosenTarget){ 
          type = rand.Next(TargetCount); 
         } 

         matrix[x, y] = new Test5Target(rand.Next(TargetCount), UseAdvancedTargets); 
        } 
       } 
      } 

      return; 
     } 
     else 
     { 
      int[] TargetsPerQuadrant = { targets/4, targets/4, targets/4, targets/4 }; 
      int RemaindingTargets = targets % 4; 
      Random rand = new Random(); 
      while (RemaindingTargets > 0) 
      { // Randomly select quadrants to allocate the Remainding targets (one may end up with 3 extra as it is now) 
       TargetsPerQuadrant[rand.Next(4)]++; 
       RemaindingTargets--; 
      } 
      PopulateQuadrants(ref matrix, xBeginQuadrant, xEndQuadrant/2, yBeginQuadrant, yEndQuadrant/2, TargetsPerQuadrant[0]); 
      PopulateQuadrants(ref matrix, xEndQuadrant/2, xEndQuadrant, yBeginQuadrant, yEndQuadrant/2, TargetsPerQuadrant[1]); 
      PopulateQuadrants(ref matrix, xBeginQuadrant, xEndQuadrant/2, yBeginQuadrant, yEndQuadrant/2, TargetsPerQuadrant[2]); 
      PopulateQuadrants(ref matrix, xEndQuadrant/2, xEndQuadrant, yBeginQuadrant/2, yEndQuadrant, TargetsPerQuadrant[3]); 
     } 
    } 

Есть ли математически правильные или простые или что-то вроде этого, или я должен продолжать идти таким образом.

Answer 1

Я, наконец, решил разместить по крайней мере четверть всех элементов в каждом углу в случайном порядке, а остаток также случайным образом игнорирует нечетные длины или просто позволяет ему перекоситься в сторону или в другую сторону.

private Element[,] GetCancellationTestMatrix(int rows, int columns, int targets, int types) 
    { 
     // Supposing the different types of elements are just ints and we want a concrete type 
     // for our targets which is contained in the variable "TargetType" 
     Element[,] Matrix = new int[rows, columns]; 

     Random rand = new Random(); 
     int currQuadRowBegin = 0; 
     int currQuadRowEnd = rows/2; 

     int currQuadColBegin; 
     int currQuadColEnd; 

     int rowIndex; 
     int colIndex; 
     for (int i = 0; i < 2; i++) 
     { 
      currQuadColBegin = 0; 
      currQuadColEnd = columns/2; 
      for (int j = 0; j < 2; j++) 
      { 
       for (int t = 0; t < targets/4; t++) 
       { 
        rowIndex = rand.Next(currQuadRowBegin, currQuadRowEnd); 
        colIndex = rand.Next(currQuadColBegin, currQuadColEnd); 
        while (Matrix[rowIndex, colIndex] != null) 
        { 
         rowIndex = rand.Next(currQuadRowBegin, currQuadRowEnd); 
         colIndex = rand.Next(currQuadColBegin, currQuadColEnd); 
        } 
        Matrix[rowIndex, colIndex] = new Element(TargetType); 
       } 
       currQuadColBegin = currQuadColEnd++; 
       currQuadColEnd = columns - 1; 
      } 
      currQuadRowBegin = currQuadRowEnd++; 
      currQuadRowEnd = rows - 1; 
     } 

     // Some targets may be unarranged yet (up to three) 
     int remainding = targets % 4; 
     while (remainding > 0) 
     { 
      rowIndex = rand.Next(0, rows); 
      colIndex = rand.Next(0, columns); 
      while (Matrix[rowIndex, colIndex] != null) 
      { 
       rowIndex = rand.Next(0, rows); 
       colIndex = rand.Next(0, columns); 
      } 
      Matrix[rowIndex, colIndex] = new Element(TargetType); 
      remainding--; 
     } 

     // Fill the remainding elements of the target matrix with other targets 
     List<int> fakeTargets = new List<int>(rows * columns - targets); 
     // If we are placing 10 targets in a 9x6 matrix then we need to place an extra 
     // 9 * 6 - 10 = 34 targets and if we have, say, 4 types then we can divide that 
     // between 4-1 (for the target type) 
     int targetsOfEachType = (rows * columns - targets)/types-1; 
     for (int i = 0; i < types; i++) 
     { 
      if (i == TargetType) continue; 
      for (int j = 0; j < targetsOfEachType; j++) 
      { 
       fakeTargets.Add(i); 
      } 
     } 
     int tmp; 
     while (fakeTargets.Count < rows * columns - targets) 
     { 
      tmp = rand.Next(types); 
      while (tmp == TargetType) 
      { 
       tmp = rand.Next(types); 
      } 
      fakeTargets.Add(tmp); 
     } 
     Shuffle(fakeTargets); // Assume this method shuffles the list of fakeTargets 
     tmp = 0; 
     for (int i = 0; i < rows; i++) 
     { 
      for (int j = 0; j < columns; j++) 
      { 
       if (Matrix[i, j] != null) continue; 
       Matrix[i, j] = new Element(fakeTargets[tmp++]); 
      } 
     } 
     return Matrix; 
    } 

Конечно, я не утверждаю, что это хорошее решение, только один, который работает для меня, по крайней мере на данный момент. Я оставлю некоторое время, чтобы кто-то мог опубликовать лучший ответ или некоторые исправления по моему, прежде чем я проверю это как ответ.