Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → C++ → Порівняння матриць
Для відправлення відповіді ви повинні увійти або зареєструватися
Дано декілька матриць 2 на 2, кожна у формі одновимірного масиву.
Треба з'ясувати скільки там різних матриць
за умови що якщо обертати одну з матриць на 90, 180 і 270 вправо,
вона може виявитися рівною іншій матриці.
Чи можна якось порівняти такі матриці без обертання?
Можливо, є якийсь унікальний для кожної матриці коефіцієнт, який можна обчислити?
Якщо і є, то він має містити не менше ніж 4*n-2 біти (де довжина кожного числа - n біт), бо матрицю можна обертати 4 способами, що усуває 2 біти.
Спробуємо так. Знаходимо максимальне число в матриці. За годинниковою стрілкою від (0,0) обираємо перше положення, де максимальне в лівому верхньому кутку. Це буде нормальна форма матриці. А тепер порівнюєте лише нормальні форми. Якщо хочете їх у числа запхати - ласкаво прошу, для 32-бітних int-ів матимете 128-бітні числа.
Ем... ні, не так. Знаходимо перше положення з можливих поворотів у лексикографічному порядку. Правда, доведеться все одно кілька порівнянь всередині матриці зробити, зате між різними матрицями - лише одне!
Чи можна якось порівняти такі матриці без обертання?
Можливо, є якийсь унікальний для кожної матриці коефіцієнт, який можна обчислити?
Ні, не існує такого коефіцієнта, котрим можна було б замінити обертання. А от зменшити кількість обертів можна, просумувавши елементи матриці. Якщо сума елементів матриць відрізняється, то матриці точно є не рівними та можна їх не обертати (тут як не обертай сума елементів матриці все одно буде однаковою).
Ну а порівняти масив із чотирьох елементів, можна використати функцію memcmp
memcmp(a, b, sizeof(int) * 4) == 0, де a та b матриці розміром 2x2, котрі представлені як одномірний масив (тип звісно int, якщо елементи матриці є цілочисельні елементи!)
Сума - досить слабка геш-функція. І все одно потім треба перевіряти, бо колізії будуть.
Teg Miles, у вас проблема цикл для порівняння матриць написати?
Teg Miles, у вас проблема цикл для порівняння матриць написати?
Ні, ось яке рішення в мене вийшло, враховуючи всі особливості завдання:
int count_different_matrices(const std::vector<std::array<int, 4>> &matrices) {
int row_size = matrices.size();
bool loop_break { false };
std::vector<std::array<int, 4>> first { matrices.at(0) };
for (int i = 1; i < row_size; ++i) {
std::array<int, 4> second = matrices.at(i);
for (int k = 0; k < 4; ++k) {
std::swap(second.at(1), second.at(2));
std::swap(second.at(0), second.at(1));
std::swap(second.at(2), second.at(3));
for (unsigned long m = 0; m < first.size(); ++m) {
if (second == first.at(m)) {
loop_break = true;
break;
}
if (k == 3 && second != first.at(first.size() - 1)&& std::find(first.begin(), first.end(), second) == first.end()) {
first.push_back(second);
}
}
if (loop_break) {
loop_break = false;
break;
}
}
}
return first.size();Завдання звідси https://www.codewars.com/kata/635fc0497dadea0030cb7936
Teg Miles написав:Чи можна якось порівняти такі матриці без обертання?
Можливо, є якийсь унікальний для кожної матриці коефіцієнт, який можна обчислити?Ні, не існує такого коефіцієнта, котрим можна було б замінити обертання. А от зменшити кількість обертів можна, просумувавши елементи матриці. Якщо сума елементів матриць відрізняється, то матриці точно є не рівними та можна їх не обертати (тут як не обертай сума елементів матриці все одно буде однаковою).
Ну а порівняти масив із чотирьох елементів, можна використати функцію memcmpmemcmp(a, b, sizeof(int) * 4) == 0, де a та b матриці розміром 2x2, котрі представлені як одномірний масив (тип звісно int, якщо елементи матриці є цілочисельні елементи!)
Думав про суми, але все одно треба забагато перевірок робити, тому відкинув цю ідею.
Мій розв'язок звідти:
bool are_same(std::array<int, 4> left, const std::array<int, 4>& right) {
for(int r=0;r<4;++r) {
if(left==right)
return true;
int t = left[0];
left[0] = left[2];
left[2] = left[3];
left[3] = left[1];
left[1] = t;
}
return false;
}
int count_different_matrices(const std::vector<std::array<int, 4>> &matrices) {
int count = 0;
for(size_t i=0; i<matrices.size(); ++i)
if(!std::any_of(matrices.begin()+i+1, matrices.end(), [&](const auto&m){return are_same(matrices[i],m);}))
count++;
return count;
}Мій розв'язок звідти:
bool are_same(std::array<int, 4> left, const std::array<int, 4>& right) { for(int r=0;r<4;++r) { if(left==right) return true; int t = left[0]; left[0] = left[2]; left[2] = left[3]; left[3] = left[1]; left[1] = t; } return false; } int count_different_matrices(const std::vector<std::array<int, 4>> &matrices) { int count = 0; for(size_t i=0; i<matrices.size(); ++i) if(!std::any_of(matrices.begin()+i+1, matrices.end(), [&](const auto&m){return are_same(matrices[i],m);})) count++; return count; }
Бачу по циклам, що у вас краще, але своє рішення я принаймні розумію:).
Трохи переробив, щоб без змін:
bool are_same(const std::array<int, 4> &left, const std::array<int, 4>& right) {
int order[4] {0,1,3,2};
for(int rotation=0; rotation<4;++rotation) {
bool equal = true;
for(int i=0; equal && i<4; ++i)
equal = (left[order[i]]==right[order[(rotation+i)%4]]);
if(equal)
return true;
}
return false;
}Одразу ідея - замість залишку збільшити масив order:
bool are_same(const std::array<int, 4> &left, const std::array<int, 4>& right) {
int order[] {0,1,3,2,0,1,3};
for(int rotation=0; rotation<4;++rotation) {
bool equal = true;
for(int i=0; equal && i<4; ++i)
equal = (left[order[i]]==right[order[rotation+i]]);
if(equal)
return true;
}
return false;
}Трохи пітончика
def hash(matrix):
ROTATION = [0,1,3,2,0,1,3]
return min(tuple(matrix[r] for r in ROTATION[rot:rot+4]) for rot in range(4))
def count_different_matrices(matrices):
return len(set(hash(m) for m in matrices))
Я хотю бачити красу і симетрію, шось типу такого :
#include <vector>
#include <array>
using arr_t = std::array<int, 4>;
using vec_t = std::vector<arr_t>;
static vec_t const rot = {
{ 0, 1, 2, 3 },
{ 2, 0, 3, 1 },
{ 1, 3, 0, 2 },
{ 3, 2, 1, 0 },
};
static arr_t const &ord = rot.front();
bool same(arr_t const &a, arr_t const &b) {
return std::any_of(rot.cbegin(), rot.cend(), [&a, &b](arr_t const &x) {
return std::all_of(ord.cbegin(), ord.cend(), [&a, &b, &x](int const i) {
return a[i] == b[x[i]];
});
});
}
int count_different_matrices(vec_t &m) {
for(auto b = m.begin(); ++b != m.end(); )
for(auto a = m.begin(); a != b; ++a)
if(same(*a, *b)) {
m.erase(b--);
break;
}
return m.size();
}Але мені не подобається складність O(n^2) в такому рішеню.
Але мені не подобається складність O(n^2) в такому рішеню.
Ага, я щойно переробив старий розв'язок на С на O(n log(n)).
Як тобі вдалось досягнути 1 kyu ?
Ну от власне так і вдалось
Переклав кату на Rust.
Людини кажуть шо це не читабельно.
Та коментарі були б незайві
Він якимись збоченнями формує число з матриці (виходячи з того, що елементи матриці не більші за 9), пхає те число до unordered_set, а потім видаляє з тієї множини по 4 можливі зсуви того числа.
n (3 << n & 0xC)
0 0
1 4
2 12
3 8Це ж O(n)
Так, дякую, дійсно, я допустив помилку в оцінку.
Моя память трохи потекла і я думав що erase займе O(log(n)), але для unordered_set це не так.
std::set<key>::erase : O(log(n))
Та коментарі були б незайві
Там все досить просто
Так ми отримали цикл [0,1,3,2]. Загалом є 8 подібних перестановок, і ця виглядає найпростішою за кількістю операторів в коді.
формує число з матриці (виходячи з того, що елементи матриці не більші за 9), пхає те число до unordered_set, а потім видаляє з тієї множини по 4 можливі зсуви того числа.
Так, дійсно, це важлива деталь.
Для відправлення відповіді ви повинні увійти або зареєструватися