1

I have N matrices (n × m) and items to place in each one (n · m). The same items are repeated randomly for each matrix. When one item is placed in (i, j), for the following matrices the item cannot be placed in the same row or column.

For example:

A 3 × 3 matrix is repeated 3 times. We have 9 items (A, B, …, I). In the first step, I add A randomly to the matrix 1 to the position (1, 2). Now with the second matrix, A cannot be placed in column 1 or row 2, they need to be excluded from the randomly selected positions.

Is there a known algorithm I can use for this or what solutions can you propose?

  • You could just rotate the rows and columns, but that wouldn't make the individual matrices very “random”. – 5gon12eder Apr 18 '16 at 11:19
  • what do you mean with rotate rows and columns? remember that you can have N repetitions of the matrices. Also I need to randomize – user1532587 Apr 18 '16 at 12:09
  • That means if you put A in (1,2) then in the 2nd grid it goes to (2,3) and in the 3rd in (3,1). To produce the 2nd grid, move each row down 1 row and move the last row to the top, then do the same for the columns. Repeat for the subsequent grids. This works as long as N<=n and N<=m. But assumes all grids have the same number of each element. – Florian F Apr 18 '16 at 12:31
  • this is a very simple and easy solution. The only missing would be have a more random distribution. – user1532587 Apr 18 '16 at 12:56
  • Maybe you should better specify your requirement for "randomness". – Florian F Apr 18 '16 at 20:20
1

What I've meant with my comment was the following simple algorithm.

Let nN and V = {1, …, n} be your set of items. To generate n × n matrices M(1) , … M(n) with the desired property, pick the elements of M(1) randomly from V without repetition. Then generate M(i + 1) by rotating the rows and columns of M(i).

By rotating the rows of matrix M I mean that the elements of the old row i become the elements of the new row i + 1 and the elements of the old row n become the elements of the new row 1. Rotating the columns happens likewise.

Illustrated by example:

 A B C                                     G H I
 D E F     -----  rotate rows  ----->      A B C
 G H I                                     D E F

   |
 rotate
 columns
   |
   V

 C A B
 F D E
 I G H

I have implemented a quick version of this in C++.

int
main()
{
  constexpr auto N = std::size_t {3};
  std::array<char, N * N> items;
  std::array<square_matrix<char, N>, N> matrices;
  auto rndeng = std::default_random_engine {std::random_device {}()};
  std::iota(std::begin(items), std::end(items), 'A');
  std::shuffle(std::begin(items), std::end(items), rndeng);
  std::copy(std::begin(items), std::end(items), std::begin(matrices.front()));
  for (auto& matrix : matrices)
    {
      matrix = matrices.front();
      rotate_rows(matrices.front());
      rotate_cols(matrices.front());
    }
  assert(is_valid(items, matrices));
  for (const auto& matrix : matrices)
    std::cout << matrix << '\n';
}

Where the acceptance criterion is defined in is_valid like this

template <typename T, std::size_t N>
bool
is_valid(const std::array<T, N * N>& items,
         const std::array<square_matrix<T, N>, N>& matrices)
{
  for (const auto& item : items)
    {
      std::array<std::size_t, N> at_row;
      std::array<std::size_t, N> at_col;
      for (auto idx = std::size_t {}; idx < N; ++idx)
        {
          const auto at = find_item(matrices[idx], item);
          if (at == std::make_pair(N, N))
            return false;
          at_row[idx] = at.first;
          at_col[idx] = at.second;
        }
      for (auto i = std::size_t {}; i < N; ++i)
        {
          if (std::count(std::begin(at_row), std::end(at_row), i) != 1)
            return false;
          if (std::count(std::begin(at_col), std::end(at_col), i) != 1)
            return false;
        }
    }
  return true;
}

using the following helper function find_item.

template <typename T, std::size_t N>
auto
find_item(const square_matrix<T, N>& matrix, const T& item)
{
  for (auto i = std::size_t {}; i < matrix.rows(); ++i)
    {
      for (auto j = std::size_t {}; j < matrix.cols(); ++j)
        {
          if (matrix(i, j) == item)
            return std::make_pair(i, j);
        }
    }
  return std::make_pair(matrix.rows(), matrix.cols());
}

The code for rotate_rows and rotate_cols is given here.

template <typename T, std::size_t N>
void
rotate_rows(square_matrix<T, N>& matrix)
{
  for (auto j = std::size_t {}; j < matrix.cols(); ++j)
    {
      const auto temp = matrix(matrix.rows() - 1, j);
      for (auto i = std::size_t {matrix.rows() - 1}; i > 0; --i)
        matrix(i, j) = matrix(i - 1, j);
      matrix(0, j) = temp;
    }
}

template <typename T, std::size_t N>
void
rotate_cols(square_matrix<T, N>& matrix)
{
  for (auto i = std::size_t {}; i < matrix.rows(); ++i)
    {
      const auto temp = matrix(i, matrix.cols() - 1);
      for (auto j = std::size_t {matrix.cols() - 1}; j > 0; --j)
        matrix(i, j) = matrix(i, j - 1);
      matrix(i, 0) = temp;
    }
}

Finally, I'm using the following simple square_matrix type.

template <typename T, std::size_t N>
class square_matrix final
{
 private:

  std::array<T, N * N> data_;

 public:

  std::size_t rows() const noexcept { return N; }
  std::size_t cols() const noexcept { return N; }

  T&
  operator()(const std::size_t i, const std::size_t j)
  {
    assert((i < this->rows()) && (j < this->cols()));
    return this->data_[i * this->rows() + j];
  }

  const T&
  operator()(const std::size_t i, const std::size_t j) const
  {
    assert((i < this->rows()) && (j < this->cols()));
    return this->data_[i * this->rows() + j];
  }

  auto begin() { return this->data_.begin(); }
  auto end() { return this->data_.end(); }

  auto begin() const { return this->data_.begin(); }
  auto end() const { return this->data_.end(); }

};

template <typename T, std::size_t N>
std::ostream&
operator<<(std::ostream& os, const square_matrix<T, N>& mat)
{
  for (auto i = std::size_t {}; i < mat.rows(); ++i)
    {
      for (auto j = std::size_t {}; j < mat.cols(); ++j)
        os << ' ' << mat(i, j);
      os << '\n';
    }
  return os;
}

If you want to make the result less predictable, you can additionally shuffle the generated matrices after you're done.

  • shuffling matrix is an important part of this solution – user1532587 Apr 18 '16 at 14:38
0

There are (n x m)! permutations of the elements, which we can assign an index to each:

1, 2, 3, ..., (n x m)!

For example if we have a 2 x 2 matrix, we will have (2 x 2)! or 24 permutations:

 1. A B C D
 2. A B D C
 3. A C B D
 4. A C D B
 5. A D B C
 6. A D C B
 7. B A C D
 8. B A D C
 9. B C A D
10. B C D A
11. B D A C
12. B D C A
13. C A B D
14. C A D B
15. C B A D
16. C B D A
17. C D A B
18. C D B A
19. D A B C
20. D A C B
21. D B A C
22. D B C A
23. D C A B
24. D C B A

So all we need to is to randomly select (without replacement) N of these permutations, one per matrix. See this answer for ideas on how to do this.

Once you have selected your permutations indices, say (1, 18, 23) for N=3, you can then find the corresponding permutations as outlined in this answer.

  • It does not take into account the no repeat column and row condition right? – user1532587 Apr 18 '16 at 14:37
  • Yes you're right. – WaelJ Apr 18 '16 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.