Quello che intendevo con il mio commento era il seguente semplice algoritmo.
Let n ∈ N 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).
Con ruotando le righe della matrice M intendo che gli elementi della vecchia riga i diventano gli elementi della nuova riga i + 1 e gli elementi della vecchia riga n diventano gli elementi della nuova riga 1. La rotazione delle colonne avviene allo stesso modo.
Illustrato dall'esempio:
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
Ho implementato una versione veloce di questo 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';
}
Dove il criterio di accettazione è definito in is_valid come questo
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;
}
utilizzando la seguente funzione di aiuto 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());
}
Il codice per rotate_rows e rotate_cols è indicato qui.
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;
}
}
Infine, sto utilizzando il seguente semplice tipo square_matrix .
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;
}
Se vuoi rendere il risultato meno prevedibile, puoi anche mescolare le matrici generate dopo aver finito.