PicoPicoRobotWoman Sep 10 at 17:18

Поиск всех последовательностей чисел от 1 до n, где сумма соседних чисел является квадратом

Easy

6 min

7.8K

Programming*Algorithms*Scala*Mathematics*Functional Programming*

Comments 32

xi-tauw Sep 10 at 18:52

наивный подход предполагает перебор всех возможных последовательностей, однако, этот метод предпологает перебор n!

Мне кажется вы недооцениваете наивность. Даже очень наивный программист не будет строить сначала факториал всех последовательностей, а потом их проверять. По мне, наивный метод будет заключаться в попытках на каждом шаге просто поставить все возможные числа, которые дают квадрат (в сумме с предыдущим) и не были уже использованы.

А чем ваш метод отличается от того, что я написал выше? Возможность выбрать следующее число в цепочке вы берете через матрицу. Выглядит как вполне компромисс проверки квадратности не через сумму, а через пространство (память). Хз, как по мне, предварительный расчет возможных квадратов уже достаточен для оптимизаций, вряд ли операция суммы настолько затратнее индекса.

nickolaym Sep 10 at 21:14

Казалось бы,

1) получаем множество квадратов $S = \{ x^2 | 1 \le x^2 \le 2n \}$

2) получаем таблицу смежности $A = \{x : \{y | x+y \in S, 1 \le y \le n\} | 1 \le x \le n\}$

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.$

4) запускаем её для всех стартовых значений

$f(x, \{x\}) | \forall x \in \{1..n\}$

Это будет тупой перебор, но в нём не будет ничего лишнего :)

Представление таблицы смежности как двоичной матрицы - не очень эффективно, потому что заставит бегать по строке матрицы, в которой порядка √n единичек и (n-√n) ноликов.

Imaginarium Sep 11 at 04:31

Простите, а что у Вас в верхнем выражении за фигурной скобкой написано?

lrdprdx Sep 11 at 10:25

Не понятно или не видно ?

Imaginarium Sep 11 at 23:38

Вижу там просто [], не могу понять

lrdprdx Sep 12 at 06:52

wataru Sep 12 at 11:23

Это типа пустой список. К [x] в этом случае ничего не дописывается.

lrdprdx Sep 13 at 08:08

Абсолютно верно. Т.е. если больше нет чисел, чтобы дать квадрат, то заканчивается последовательность на этом.

nickolaym Sep 11 at 17:18

Множество чисел, являющихся квадратами натуральных чисел, и лежащих в диапазоне от 1 до 2n. Потому что для пар чисел (x,y) из диапазона от 1 до n, их сумма лежит в диапазоне.... а, ну да, конечно, от 2 до 2n.

lrdprdx Sep 11 at 10:24

Во-первых, спасибо за символьное описание. Намного меньше вопросов вызывает. Во-вторых, солидарен с таким подходом - тут сразу руки чешутся рекурсию написать. В-третьих, NIT, я бы квантор всеобщности местами убрал.

Ну и P.S. в языках без хвостовой рекурсии, корутин и т.д. придется в цикл всё переводить. Но рассуждать и строить решения в рамках рекурсии, а потом переводить в цикл, мне кажется, проще в таких задачах.

nickolaym Sep 11 at 17:22

Функция многозначная, поэтому и квантор. Ну да я особо не задумывался о красивой нотации. Можно переписать в виде однозначной функции, возвращающей множество цепочек.

В языках с генераторами списков удобно иметь дело с многозначностью, нежели энергично рожать множества.

wataru Sep 10 at 23:37

Вы в правильную сторону думаете: надо построить граф, где вершины - числа, а ребра есть между двумя числами, если их сумма - квадрат. В графе будет что-то порядка 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 Sep 11 at 10:36

За такое время, кажется, можно найти один путь.

А вот всего путей может быть аж (sqrt(n)!)^sqrt(n), что примерно (n/c)^(n/2) (и гораздо больше чем n^3 * 2^n): если граф распадается на почти полные компоненты по sqrt(n) вершин, где у каждой компоненты есть "первая" и "последняя", при этом "последняя" очередной компоненты связанна с "первой" следующей. По каждой компоненте будет sqrt(n)! путей, компонент sqrt(n), что даёт оценку вначале.

wataru Sep 11 at 11:16

В этом графе путей будет сильно меньше, чем n^3 2^n, ибо тут не произвольный граф с n*sqrt(n) ребрами, из которых можно собирать компоненты с кучей возможных путей. Ребра как-то более менее равномерно размазаны по всему графу. Поэтому эту часть я даже не считал.

lightln2 Sep 11 at 16:04

А почему у Вас получилась такая оценка? всего 2^n вариантодля еще a,b дают n^2 , и для построения каждого F(S,a,b) надо примерно $\sqrt{n}$ операций (примерное количество ребер из ). То есть, получается $O(n^{2.5} 2^n)$
И кажется, можно обойтись без - если взять F(S, a) - количество гамильтоновых путей в , начинающихся в .

wataru Sep 11 at 16:21

Я сильно сверху оценивал количество вариантов для следующей вершины. Так-то, вы правы, можно и корнем ограничиться. И вторая ваша идея тоже отличная. Действительно, не важно же где путь закончится, мы все-равно все возможные концы перебираем. В итоге вы степень n до 1.5 уменьшили.

lightln2 Sep 15 at 16:04

Некий китаец посчитал количество решений до n=59 (oeis.org/A071983), и у меня нет идей, как он в принципе мог это сделать.
Там похоже, что количество решений растет как 4^n, поэтому любое перечисление решений будет неэффективно.
Тем не менее, простой DFS с оптимизациями (представление ребер графа и подмножеств вершин битовыми масками) на практике оказался почти самым быстрым: 4 часа для n=46 (во всех алгоритмах я считаю однопоточное исполнение). До этого его скорость растет примерно как 3^n, но понятно, что на больших n она выростет как минимум до 4^n.

DP оказалось неэффективно: для n=39 у меня уже не хватает памяти (растет экспоненциально), а решение для n=38 занимает 4.5 минуты.

Самое эффективное решение, которое я нашел, - комбинация DFS и DP: для нечетного n ищем с помощью DFS количество цепочек F(a, S), начинающихся в a, для всех подмножнств S мощности (n+1)/2. Эти позволяет рассчитать количество гамильтоновых путей, имеющих a ровно посередине. Ищет n=47 за 6 часов, до этого растет примерно как (1.7)^n. К сожалению, память растет тоже экспоненциально (но медленнее, чем стандартный DP).

Самый лучший теоретический алгоритм основан на принципе inclusion/exclusion, он имеет сложность (2^n)*(n^3) при полиномиальной памяти, но он требует возведения матриц nxn в степень n, поэтому он на практике слишком медленный (реализация на питоне не доходит даже до n=30). Рано или поздно он обгонит по скорости все прочие алгоритмы, но, скорее всего, время работы будет превышать время существование вселенной.
Для этого алгоритма, правда, есть огромное поле оптимизаций (полное распараллеливание на 2^n умножений матриц, которые можно делать на GPU) - но по моим подсчетам, все равно будет слишком медленно, если только не найти эвристик, которые позволят не считать большую часть подмножеств.

nickolaym Sep 11 at 17:36

Это не совсем задача коммивояжёра. Тут строятся все пути, включая и не проходящие через все вершины. Разнообразные тупики тоже допускаются.

Например, пусть у нас 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

wataru Sep 11 at 17:56

включая и не проходящие через все вершины.

В условии:
> оследовательность должна состоять из всех чисел от 1 до n

nickolaym Sep 11 at 18:06

А, упс. Ну в таком случае для некоторых n решения тупо нет.

alexluk86 Sep 11 at 05:28

Зачем матрица с суммами 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 Sep 11 at 08:23

Я тоже так сначала подумал. Фишка в том, что соседними числа должны быть не в диапазоне, а в найденной последовательности, на это намекает первая пара результата 16 и 9 на скриншоте.

alexluk86 Sep 11 at 12:22

Хорошо. Если нужны все возможные варианты пар чисел из диапазона 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 Sep 11 at 12:40

Надо же их все n разных чисел в последовательность составить. Вы этим циклом вывели все ребра в графе, а вам надо найти все Гамильтоновы пути в графе.

Dinxor Sep 11 at 16: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. А вы заметили, что на скриншоте с результатами вторая последовательность - это первая, развёрнутая в обратную сторону?

nilluf Sep 11 at 17:34

кому эта хрень нужна? где ее применить в жизни?

nickolaym Sep 11 at 17:42

Есть ли какой-нибудь изящный способ перечислить все наиболее длинные цепочки неповторяющихся чисел для произвольной матрицы смежности? Или для конкретно этой?

Не тупым перебором с последующей сортировкой и фильтрацией.

wataru Sep 11 at 18:01

перечислить все наиболее длинные цепочки неповторяющихся чисел для произвольной матрицы смежности

Есть Динамическое Программирование (смотрите мой пост выше). Кроме этого остается перебор с отсечениями и различные его вариации.

Конкретно для этой матрицы смежности, возможно, могут быть более хитрые решения. Граф не очень плотный. Можно, например, посмотреть на компоненты двусвязности, вдруг граф распадается на путь и там понятно, где надо начать и закончить в каждой компоненте.

Naf2000 Sep 11 at 21:10

Начал тупо рисовать на бумаге. Связность графа образуется только при n=14. При n=15, 16, 17 появились гамильтоновы пути - наши решения. Однако при n=18..21 их снова нет. Интрига...

PicoPicoRobotWoman Sep 11 at 21:24

...

Anilarion Sep 12 at 08:41

Если сформулировать задачу по другому - у вас есть граф, в котором вершины имеют значения от 1 до N, а ребра проходят между вершинами, в сумме дающими квадрат. В общем смысле, вы пытаетесь найти все гамильтоновы пути данного графа (но вы также должны доказать, что для конкретного числа в принципе есть такой путь, потому что это не гарантируется для графа, например для 14 или для 22).
Но даже поиск одного гамильтонова пути не эвристическими методами будет занимать много времени, как, например, задача на CodeWars: https://www.codewars.com/kata/5a667236145c462103000091 .
На нём, кстати, дается уточнение, что вы не решите эту задачу для чисел больше 50 в лоб. Т.е. вы не сможете алгоритмически найти ВСЕ такие пути в графе. А для маленьких чисел вы можете сделать обход в ширину для каждой вершины.

xl_lx Sep 27 at 00:15

А не могли бы вы для джунов выложить тесты. Хоть на github.

Мой вариант кода

import scala.io.StdIn.readInt

val userInput = readInt.abs

val pairs: Seq[(Int, Int)] = for {
  sq <- (2 to userInput).map(x => x * x)
  if (sq <= 2*userInput - 1)
  ps <- (1 to userInput).map(x => (x, sq-x))
  if (ps._2 > 0) & (ps._1 != ps._2) & (ps._1 <= userInput & ps._2 <= userInput) 
} yield ps

val matrix: Map[Int, Seq[Int]] = pairs.groupMap(_.1)(._2)

def findAllChains(ms: Map[Int, Seq[Int]]): List[Seq[Int]] = {
  def loop(cursor: Int, acc: Seq[Int] = Nil, nums: Seq[Int]): List[Seq[Int]] = {
    val numsToChain = ms(cursor).filter(x => nums.contains(x)).toList
    if numsToChain.isEmpty then List(acc)                                       
    else                                                                        
      numsToChain.flatMap(x => loop(x, acc ++ Seq(x), nums.filter(_ != x)))
  }
  val allNums = ms.keys.toList
  allNums.flatMap(x => loop(x, Seq(x), allNums.filter(_ != x)))
}

findAllChains(matrix).filter(_.size == userInput).foreach(println)