Ремарка
В данной статье представлено решение задачи по нахождению всех возможных цепочек чисел в матрице, соответствующих определенным условиям. Однако следует отметить, что это решение не претендует на звание оптимального. Подход, описанный здесь, может иметь свои ограничения и не всегда быть самым эффективным для всех возможных сценариев. Автор не утверждает, что предложенный метод является наилучшим или универсальным способом решения подобных задач. Важно понимать, что существует множество альтернативных подходов, и оптимальное решение может варьироваться в зависимости от конкретных требований и условий задачи.
Описание задачи
Необходимо найти все возможные последовательности чисел от 1 до n (задает пользователь), удовлетворяющие следующему условию: сумма двух соседних чисел в последовательности должна быть квадратом целого числа.
Формальные требования:
-
Входные данные:
Натуральное число
n, определяющее диапазон чисел от 1 доn(где n≥1n \geq 1n≥1).
-
Выходные данные:
Список всех возможных последовательностей чисел от 1 до
n, где сумма двух соседних чисел в последовательности является квадратом целого числа (далее квадратное число или аналогично).
-
Ограничения:
Последовательности должны включать только числа от 1 до
nбез повторений.последовательность должна состоять из всех чисел от 1 до
n
Оптимизация поиска с помощью матрицы связей
наивный подход предполагает перебор всех возможных последовательностей, однако, этот метод предполагает перебор n!, последовательностей, что очень много даже при относительно малых n и соответственно не быстро и может памяти не хватить.
Чтобы улучшить производительность и сократить количество проверяемых вариантов, используется матрицу связей. Эта матрица помогает существенно снизить количество комбинаций, которые необходимо проверять, за счет предварительного анализа допустимых переходов между числами.
Построение матрицы связей
Определение квадратных чисел: Сначала необходимо определить все возможные квадратные числа, которые могут быть результатом суммы двух чисел от 1 до
n. Это делается для того, чтобы упростить проверку условий при построении матрицы связей.Создание матрицы связей: Мы создаем матрицу
n×n, где элемент в позиции(i,j)равенtrue, если сумма чиселiиjявляется квадратом целого числа. В противном случае, элемент равенfalse. Это позволяет нам легко и быстро проверять, допустим ли переход от числаiк числуjв последовательности.Использование матрицы для генерации последовательностей: Используя построенную матрицу связей, мы можем находить все возможные последовательности. Начав с любого числа, мы проверяем матрицу, чтобы определить, к каким числам можно перейти на основе условия, что сумма должна быть квадратом. Это значительно сокращает количество вариантов и упрощает процесс поиска.
реализации алгоритма на Scala
для начала нужно определить все возможные комбинации из двух чисел которые могут дать квадратное число , стоит заметить что для произвольного натурально n, квадратные числа могут быть больше самого n (так для n = 15 есть пары дающие 25 в сумме, например 12 и 15) и таким образом надо смотреть все возможные пары для чисел меньших или равных 2 * n - 1 (поскольку это максимальная сумма которая может быть
//метод для поиска всех квадратных числе возможны, которые можно соствит из чисел от 1 до n
def squareNumbersLessThan(n: Int): Seq[Int] = {
//начинаю с 2, поскольку 1 в этой задаче не интересует
//ищу до корня из n поскольку оно и покажыт максимальный корень округленый в лево
//и соответственно можно построить все числа квадратные до него
(2 to math.sqrt(n).toInt).map(x => x * x)
}
/**
* Находит все уникальные пары чисел от 1 до n, сумма которых равна n,
* при этом исключая пары, содержащие нули.
*
* Метод генерирует последовательность пар чисел (x, y) таких, что:
* - x и y — числа от 1 до n
* - сумма x и y равна n
* - x не равно y
* - x и y не равны нулю (хотя для чисел от 1 до n это условие избыточно)
*
*/
def findUniquePairsFunctional(n: Int): Seq[(Int, Int)] = {
(1 to n).map(x => (x, n - x)).filter { case (x, y) => x != y }.filter { case (x, y) => y != 0 && x != 0}
}
val n: Int = readInt()//читаем n введеное пользователем
val squares: Seq[Int] = squareNumbersLessThan(n * 2 -1) //находим все возможные квадраты
val allPairs = squares.flatMap(findUniquePairsFunctional) // находи все пары которые интересуют.
создадим матрицу и методы для работы с ней
/**
* Создает квадратную матрицу размером n x n, где все элементы инициализированы значением false.
*
* @param n Размер матрицы (число строк и столбцов).
* @return Квадратная матрица размером n x n, заполненная значениями false.
*/
def createMatrix(n: Int): Array[Array[Boolean]] = {
Array.tabulate(n, n)((_, _) => false)
}
/**
* Выводит матрицу в виде строки, где элементы 1 и 0 отображаются в виде "1" и "0" соответственно.
* Значения в строках разделены символом " | ".
*
* @param matrix Квадратная матрица значений типа Boolean.
*/
def printMatrix(matrix: Array[Array[Boolean]]): Unit = {
matrix.foreach(row => println(row.map(if (_) "1" else "0").mkString(" | ")))
}
/**
* Обновляет значение в указанной ячейке матрицы и возвращает новую матрицу.
* Создается новая копия матрицы, чтобы избежать изменения исходной матрицы.
*
* @param matrix Исходная матрица значений типа Boolean.
* @param row Индекс строки, в которой нужно обновить значение.
* @param col Индекс столбца, в котором нужно обновить значение.
* @param value Новое значение для указанной ячейки.
* @return Новая матрица с обновленным значением.
*/
def updateMatrixValue(matrix: Array[Array[Boolean]], row: Int, col: Int, value: Boolean): Array[Array[Boolean]] = {
val updatedMatrix = matrix.map(_.clone())
if (row >= 0 && row < updatedMatrix.length && col >= 0 && col < updatedMatrix(row).length) {
updatedMatrix(row)(col) = value
}
updatedMatrix
}
/**
* Находит все ячейки в указанной строке матрицы, где значение равно true.
* Возвращает список пар координат (индексов) ячеек с истинным значением.
*
* @param matrix Квадратная матрица значений типа Boolean.
* @param rowIndex Индекс строки, в которой нужно найти значения true.
* @return Последовательность пар координат (индексов) ячеек, где значение равно true.
*/
def findTrueInRow(matrix: Array[Array[Boolean]], rowIndex: Int): Seq[(Int, Int)] = {
if (rowIndex >= 0 && rowIndex < matrix.length) {
matrix(rowIndex).zipWithIndex.collect {
case (value, colIndex) if value => (rowIndex, colIndex)
}
} else {
println(s"Row index $rowIndex is out of bounds!")
Seq.empty
}
}
ну и финальный метод который и найдет все цепочки
/**
* Находит все возможные цепочки чисел в матрице, где каждое число в цепочке соединяется с другим числом,
* если их сумма является квадратом. Цепочки формируются из всех чисел от 1 до n, удовлетворяющих условиям.
*
* @param matrix Квадратная матрица значений типа Boolean, где значение true обозначает допустимое соединение
* между числами, и false обозначает отсутствие соединения.
* @return Список всех цепочек чисел, которые можно построить, начиная с любого числа и соблюдая условия соединения.
*/
def findAllChains(matrix: Array[Array[Boolean]]): List[Seq[Int]] = {
val n = matrix.length
/**
* Рекурсивная функция для поиска всех цепочек, начиная с текущего числа.
*
* @param cursor Текущее число, от которого начинается поиск.
* @param acc Накопленная цепочка чисел, которая обновляется по мере рекурсивного поиска.
* @param nums Список оставшихся чисел, которые могут быть добавлены в цепочку.
* @return Список всех цепочек, начинающихся с текущего числа.
*/
def loop(cursor: Int, acc: Seq[Int], nums: Seq[Int]): List[Seq[Int]] = {
// Находит все числа в строке `cursor`, которые могут быть добавлены в цепочку
val pairs = findTrueInRow(matrix, cursor).map(_._2).filter(num => nums.contains(num)).toList
// Если есть допустимые пары для продолжения цепочки
if (pairs.nonEmpty) {
// Рекурсивно строит цепочки, добавляя текущее число и продолжая поиск
pairs.flatMap { num =>
loop(num, acc ++ Seq(num), nums.filter(_ != num))
}
} else {
// Если нет допустимых пар, возвращает текущую цепочку как один из результатов
List(acc)
}
}
// Создает список всех чисел от 1 до n-1, для использования в качестве начальных точек цепочек
val fullNums = (1 until n).toList
// Запускает рекурсивный поиск цепочек для каждого числа, начиная с полного списка
fullNums.flatMap(num => loop(num, Seq(num), fullNums.filter(_ != num)))
}
ну и остаеться тлько вызвать метод и отсеять неподходящии по размеру цепочки
lazy val emptyMatrixPairs = createMatrix(n + 1) // создаем пустую матрицу
//заполняем матрицу
lazy val fullMatrixPairs = allPairs.foldLeft(emptyMatrixPairs) {
case (agg, (x, y)) =>
updateMatrixValue(agg, x, y, true)
}
//выведем чтоб посмотреть что там
printMatrix(fullMatrixPairs)
//получаем все квадратные цепочки и отсеиваем те что по длине меньше n
val res = findAllChains(fullMatrixPairs).filter(_.size == n)
println(res) // выводим
println(res.size) // выводим пример для n = 17
P.S. код можно глянуть тут
Комментарии (30)
nickolaym
10.09.2024 15:52+5Казалось бы,
1) получаем множество квадратов
2) получаем таблицу смежности
3) делаем рекурсивную функцию, строящую цепочки (W - множество использованных в цепочке чисел)
![f(x, W) = [x] + \left\{\begin{matrix} [] & \Leftarrow & A(x) \setminus W = \varnothing \\ f(y, W\cup \{ y \} ) & \Leftarrow & \forall y \in A(x) \setminus W \\ \end{matrix}\right.](https://habrastorage.org/getpro/habr/upload_files/52d/380/c8b/52d380c8b72627f5b18549b3b3289b89.svg)
4) запускаем её для всех стартовых значений
Это будет тупой перебор, но в нём не будет ничего лишнего :)
Представление таблицы смежности как двоичной матрицы - не очень эффективно, потому что заставит бегать по строке матрицы, в которой порядка √n единичек и (n-√n) ноликов.
Imaginarium
10.09.2024 15:52Простите, а что у Вас в верхнем выражении за фигурной скобкой написано?
lrdprdx
10.09.2024 15:52Не понятно или не видно ?
nickolaym
10.09.2024 15:52Множество чисел, являющихся квадратами натуральных чисел, и лежащих в диапазоне от 1 до 2n. Потому что для пар чисел (x,y) из диапазона от 1 до n, их сумма лежит в диапазоне.... а, ну да, конечно, от 2 до 2n.
lrdprdx
10.09.2024 15:52Во-первых, спасибо за символьное описание. Намного меньше вопросов вызывает. Во-вторых, солидарен с таким подходом - тут сразу руки чешутся рекурсию написать. В-третьих, NIT, я бы квантор всеобщности местами убрал.
Ну и P.S. в языках без хвостовой рекурсии, корутин и т.д. придется в цикл всё переводить. Но рассуждать и строить решения в рамках рекурсии, а потом переводить в цикл, мне кажется, проще в таких задачах.
nickolaym
10.09.2024 15:52Функция многозначная, поэтому и квантор. Ну да я особо не задумывался о красивой нотации. Можно переписать в виде однозначной функции, возвращающей множество цепочек.
В языках с генераторами списков удобно иметь дело с многозначностью, нежели энергично рожать множества.
wataru
10.09.2024 15:52+2Вы в правильную сторону думаете: надо построить граф, где вершины - числа, а ребра есть между двумя числами, если их сумма - квадрат. В графе будет что-то порядка n sqrt(n)/2 ребер.
Надо в этом графе найти все пути, проходящий через все вершины. Это почти что задача коммивояжора на очень специфичном графе. У вас n, похоже, весьма небольшое, поэтому лучшим решением тут было бы динамическое программирование.
F(S, a, b) - есть ли путь из a в b, проходящий через вершины из множества S. Пересчет прост: перебираем следующую вершину v в пути из S/{a,b}, в которые есть ребра из a, и смотрим, есть ли оставшийся путь через F(S/{a}, v, b}. Ну и база, когда S={a, b}.
А вот потом это ДП можно использовать для отсечения вообще всех тупиков в переборе. Перебрали начало и конец всего пути, а потом рекурсивно перебирайте следующую вершину в пути, если ДП говорит, что путь там существует.
Это все будет за O(n^3 2^n)
amishaa
10.09.2024 15:52За такое время, кажется, можно найти один путь.
А вот всего путей может быть аж (sqrt(n)!)^sqrt(n), что примерно (n/c)^(n/2) (и гораздо больше чем n^3 * 2^n): если граф распадается на почти полные компоненты по sqrt(n) вершин, где у каждой компоненты есть "первая" и "последняя", при этом "последняя" очередной компоненты связанна с "первой" следующей. По каждой компоненте будет sqrt(n)! путей, компонент sqrt(n), что даёт оценку вначале.wataru
10.09.2024 15:52В этом графе путей будет сильно меньше, чем n^3 2^n, ибо тут не произвольный граф с n*sqrt(n) ребрами, из которых можно собирать компоненты с кучей возможных путей. Ребра как-то более менее равномерно размазаны по всему графу. Поэтому эту часть я даже не считал.
lightln2
10.09.2024 15:52+1А почему у Вас получилась такая оценка? всего
вариантодля 
еще 
дают 
, и для построения каждого 
надо примерно 
операций (примерное количество ребер из 
). То есть, получается 
И кажется, можно обойтись без
- если взять 
- количество гамильтоновых путей в , начинающихся в .wataru
10.09.2024 15:52Я сильно сверху оценивал количество вариантов для следующей вершины. Так-то, вы правы, можно и корнем ограничиться. И вторая ваша идея тоже отличная. Действительно, не важно же где путь закончится, мы все-равно все возможные концы перебираем. В итоге вы степень n до 1.5 уменьшили.
nickolaym
10.09.2024 15:52Это не совсем задача коммивояжёра. Тут строятся все пути, включая и не проходящие через все вершины. Разнообразные тупики тоже допускаются.
Например, пусть у нас n=10. Тогда квадраты - это 4, 9, 16, а смежные числа -
1 -> 3, 8
2 -> 7
3 -> 1, 6
4 -> 5
5 -> 4
6 -> 3, 10
7 -> 2, 9
8 -> 1
9 -> 7
10 -> 6
Как минимум, мы видим, что граф многосвязный - есть изолированные островки {1, 3, 6, 8, 10}, {2, 7, 9} и {4, 5}.
Полный список самых длинных цепочек:
1, 3, 6, 10
1, 8
2, 7, 9
3, 1, 8
3, 6, 10
4, 5
5, 4
6, 3, 1, 8
6, 10
7, 2
8, 1, 3, 6
9, 7, 2
10, 6, 3, 1
Если избавиться от подцепочек и отзеркаливаний, то получим
8, 1, 3, 6, 10
2, 7, 9
-
4, 5
alexluk86
10.09.2024 15:52Зачем матрица с суммами i и j чисел, если требуется сумма соседних чисел и j=i+1?
К чему вообще такие сложности?
Может я чего не понял?
Квадрат натурального числа не будет больше чем 2n-1 значит можно взять цикл на round(sqrt(2n-1)/2)=m повторов и пробежаться по квадратам натуральных нечётных чисел в диапазоне от 3 до 2m+1.
For i:=1 to m
X:=(sqr((i*2)+1)-1)/2;
Print(X,X+1)
При n = 65535 получаем цикл на 128 операций.
Dinxor
10.09.2024 15:52+1Я тоже так сначала подумал. Фишка в том, что соседними числа должны быть не в диапазоне, а в найденной последовательности, на это намекает первая пара результата 16 и 9 на скриншоте.
alexluk86
10.09.2024 15:52Хорошо. Если нужны все возможные варианты пар чисел из диапазона 1..n, то дополним цикл следующими операциями
Y:=X+1;
repeat
Print (X,Y);
Print(Y,X);
Dec(X);
Inc(Y)
until (X>=1) & (Y<=n)
Цикл выдаст все возможные варианты пар чисел, сумма которых даёт квадрат натурального числа найденного в вышестоящем цикле.
Аналогичный алгоритм делается для нахождения пар чисел сумма которых равна квадрату чётного натурального числа, только Y:=Х;
В итоге затрат по памяти никаких, все вычисления выдают только правильные результаты, а значит и по времени затраты не велики.
Или я опять чего-то не понял? Тогда прошу привести контрпример в виде пары произвольных чисел от 1 до n, которые нельзя найти указанным способом.
wataru
10.09.2024 15:52Надо же их все n разных чисел в последовательность составить. Вы этим циклом вывели все ребра в графе, а вам надо найти все Гамильтоновы пути в графе.
Dinxor
10.09.2024 15:52А что если развернуть задачу в сторону суммы квадратов натуральных чисел?
1. Очевидно, что сумма последовательности чисел от 1 до n равна n*(n+1)/2. Сумма квадратов должна быть равна этой сумме или меньше неё на одно из чисел для нечётного n.
2. Количество квадратов известно - это n/2
3. Квадраты натуральных чисел можно вычислить даже без умножения как сумму натуральных нечётных чисел (ряд 1+3+5+7+9+11... на каждом шаге выдает как раз квадраты 4, 9, 16, 25, 36...). Заполняем до 2*n-1
Далее пытаемся заполнить сумму квадратами и проверяем, что используются все числа.
P.S. А вы заметили, что на скриншоте с результатами вторая последовательность - это первая, развёрнутая в обратную сторону?
nickolaym
10.09.2024 15:52Есть ли какой-нибудь изящный способ перечислить все наиболее длинные цепочки неповторяющихся чисел для произвольной матрицы смежности? Или для конкретно этой?
Не тупым перебором с последующей сортировкой и фильтрацией.
wataru
10.09.2024 15:52перечислить все наиболее длинные цепочки неповторяющихся чисел для произвольной матрицы смежности
Есть Динамическое Программирование (смотрите мой пост выше). Кроме этого остается перебор с отсечениями и различные его вариации.
Конкретно для этой матрицы смежности, возможно, могут быть более хитрые решения. Граф не очень плотный. Можно, например, посмотреть на компоненты двусвязности, вдруг граф распадается на путь и там понятно, где надо начать и закончить в каждой компоненте.
Naf2000
10.09.2024 15:52Начал тупо рисовать на бумаге. Связность графа образуется только при n=14. При n=15, 16, 17 появились гамильтоновы пути - наши решения. Однако при n=18..21 их снова нет. Интрига...
Anilarion
10.09.2024 15:52+1Если сформулировать задачу по другому - у вас есть граф, в котором вершины имеют значения от 1 до N, а ребра проходят между вершинами, в сумме дающими квадрат. В общем смысле, вы пытаетесь найти все гамильтоновы пути данного графа (но вы также должны доказать, что для конкретного числа в принципе есть такой путь, потому что это не гарантируется для графа, например для 14 или для 22).
Но даже поиск одного гамильтонова пути не эвристическими методами будет занимать много времени, как, например, задача на CodeWars: https://www.codewars.com/kata/5a667236145c462103000091 .
На нём, кстати, дается уточнение, что вы не решите эту задачу для чисел больше 50 в лоб. Т.е. вы не сможете алгоритмически найти ВСЕ такие пути в графе. А для маленьких чисел вы можете сделать обход в ширину для каждой вершины.
xi-tauw
Мне кажется вы недооцениваете наивность. Даже очень наивный программист не будет строить сначала факториал всех последовательностей, а потом их проверять. По мне, наивный метод будет заключаться в попытках на каждом шаге просто поставить все возможные числа, которые дают квадрат (в сумме с предыдущим) и не были уже использованы.
А чем ваш метод отличается от того, что я написал выше? Возможность выбрать следующее число в цепочке вы берете через матрицу. Выглядит как вполне компромисс проверки квадратности не через сумму, а через пространство (память). Хз, как по мне, предварительный расчет возможных квадратов уже достаточен для оптимизаций, вряд ли операция суммы настолько затратнее индекса.