Find all sequences of numbers from 1 to n where the sum of adjacent numbers is a square

remark:

This article presents a solution to the problem of finding all possible sequences of numbers in a matrix that meet certain conditions. However, it should be noted that this solution does not claim to be optimal. The approach described here may have its limitations and may not always be the most effective for all possible scenarios. The author does not claim that the proposed method is the best or universal way to solve such problems. It is important to understand that there are many alternative approaches, and the optimal solution may vary depending on the specific requirements and conditions of the problem.

Description of the task:

It is necessary to find all possible sequences of numbers from 1 to n (specified by the user) that satisfy the following condition: the sum of two adjacent numbers in the sequence must be the square of an integer.

Formal requirements:

  1. Input data:

  2. Output data:

    • List of all possible sequences of numbers from 1 to nwhere the sum of two adjacent numbers in a sequence is the square of an integer (hereinafter referred to as a square number or similar).

  3. Restrictions:

    • Sequences must include only numbers from 1 to n without repetitions.

    • the sequence must consist of all numbers from 1 to n

Search Optimization Using a Link Matrix

The naive approach involves enumerating all possible sequences, however, this method involves enumerating n!sequences, which are very many even for relatively small n and, accordingly, not fast and there may not be enough memory.

To improve performance and reduce the number of variants to be checked, a link matrix is ​​used. This matrix helps to significantly reduce the number of combinations that need to be checked by pre-analyzing the permissible transitions between numbers.

Construction of a connection matrix

  1. Definition of square numbers: First, we need to determine all possible square numbers that can be the result of the sum of two numbers from 1 to nThis is done in order to simplify the verification of conditions when constructing the connection matrix.

  2. Creating a connection matrix: We create a matrix n×n where the element is in position (i,j) equal trueif the sum of the numbers i And j is a square of an integer. Otherwise, the element is equal to false. This allows us to easily and quickly check whether the transition from a number is allowed i to the number j in sequence.

  3. Using a matrix to generate sequences: Using the constructed matrix of connections, we can find all possible sequences. Starting with any number, we check the matrix to determine which numbers we can move to based on the condition that the sum must be a square. This significantly reduces the number of options and simplifies the search process.

implementation of the algorithm in Scala

First, you need to determine all possible combinations of two numbers that can give квадратное число it is worth noting that for an arbitrary natural number n, square numbers can be larger than n itself (so for n = 15 there are couples that give 25 in total, for example 12 и 15) and thus it is necessary to look at all possible pairs for numbers less than or equal to 2 * n - 1 (since this is the maximum amount that can be

//метод для поиска всех квадратных числе возможны, которые можно соствит из чисел от 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) // находи все пары которые интересуют.

let's create a matrix and methods for working with it

/**
 * Создает квадратную матрицу размером 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
  }
}

Well, here is the final method that will find all the chains

/**
 * Находит все возможные цепочки чисел в матрице, где каждое число в цепочке соединяется с другим числом,
 * если их сумма является квадратом. Цепочки формируются из всех чисел от 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)))
}

Well, all that remains is to call the method and filter out the chains that are not the right size

  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) // выводим

example for n = 17

n = 17

n = 17

P.S. You can look at the code here

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *