Ответы пользователя по тегу Математические матрицы
  • Генерация всех позможных вариантов заполнения квадратной матрицы N-м числом графов. Алгоритм..?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если мы возьмём любую цепочку, проходящую через все точки (например, змейку или спираль), и разрежем её на куски всеми возможными способами, а потом часть кусков ещё и развернём, у нас уже получится примерно 2^(N^2)/3 вариантов. Уже при N=7 перечислить их нереально (при N=6 их всего 10 миллиардов - это не так много). Но поскольку исходных цепочек (проходящих через все точки) много, а кроме того, не все конфигурации можно получить разрезанием одной цепочки, вариантов будет ещё больше.
    Алгоритмы - как рекурсия, так и перебор состояний клеток - не очень сложные. В обоих случаях нужно искать разбиение на неориентированные цепочки, а потом всеми способами задавать их направление.
    В случае перебора состояний (он проще) делаем так. Замечаем, что у каждой клетки есть 10 возможных состояний - 4 для конца цепочки (направления, куда из этой клетки цепочка идёт), 4 для клетки, где цепочка поворачивает, и 2 для клетки, через которую она проходит прямо. Кроме того, есть ограничения: цепочка не может упираться в стенку, и общее ребро двух соседних клеток либо пересекается цепочкой с каждой стороны, либо нет. Ну, и не должно быть циклов.
    Алгоритм получается таким. Перебираете клетки матрицы по строкам. Для каждой очередной клетки смотрите состояние её соседей, и получаете список возможных состояний самой клетки - их не более трёх. В случае, если есть состояние, которое соединяет две соседние цепочки, надо пройтись по ним - проверить, не являются ли они концами одной цепочки (если да - получится цикл, а он запрещён). Теперь подставляем в клетку по очереди все допустимые состояния, и рекурсивно вызываем функцию перебора для следующей клетки. Когда дойдём до конца - фиксируем найденное разбиение.
    Ответ написан
  • Как легче всего решить матрицы?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Все задачи на работу со столбцами. Читаете, что бывает с определителем, когда столбец умножается на число, когда столбец прибавляется к другому, когда два столбца меняются местами, когда все элементы столбца оказываются нулевыми. И решаете, что применить.
    Ответ написан
  • Как оптимально найти подмножества в наборе данных многие-ко-многим?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Есть простое решение за (число сообществ)*(число связей "пользователь-сообщество").

    Для каждого сообщества Y:
    - заводим массив R[C], где C - число сообществ
    - для каждого пользователя X из сообщества Y:
    - - для каждого сообщества M, в которое входит пользователь X: R[M]=R[M]+1
    - для каждого сообщества M: если M!=Y и R[M] > 1, то пара (Y,M) - ядро.

    Быстрее пока не получается.
    Ответ написан
  • Как заполнить матрицу по данному образцу?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если это C++, то подойдёт такая формула:
    M[i][j]=(abs(j-i)+1)*((i+j-N+1)*(i-j)>=0)
    Если формулу хочется чисто математическую, то вместо ((i+j-N+1)*(i-j)>=0) можно написать (sign(2*(i+j-N+1)*(i-j)+1)+1)/2
    Ответ написан