Как мне найти список (мультимножество, размер n) целых чисел, где среднеквадратическое значение множества является целым числом?

Question

Я уже нашел этот

Грубая сила, конечно, возможна, но есть ли другие способы? Есть ли способ найти все мультимножества? Есть ли способ узнать, сколько комбинаций существует под определенным пределом?

Возможно, этот вопрос слишком математичен для SO, если это так, я перенесу его.

Я создал свою собственную версию в javascript, сгенерировав все возможные комбинации списка чисел, а затем проверив целочисленную RMS. Это наборы, а не мультимножества.

Answer 1

Изменить: я использовал N для суммы суммы и K для числа квадратов.

Количество мульти-множеств быстро растет, поэтому N должно иметь разумное значение. Так что эта задача эквивалентна изменению суммы N на K монет с номиналами 1,4,9,25... (и количество вариантов может быть рассчитано с использованием динамического программирования).

Самая простая реализация рекурсивна - мы просто генерируем все возможные дополнения. В моей реализации Delphi я собираю слагаемые в строку (вместо списка) для простоты.

Обратите внимание, что такая реализация может генерировать одни и те же последовательности снова и снова - примечание {5,7} Конечная последовательность в моем примере. Чтобы улучшить производительность (важно для довольно больших значений N и K), стоит хранить сгенерированные последовательности в таблице или на карте (с {N;K;Min} ключ). В этом случае генерация от больших слагаемых к меньшим была бы лучше, потому что маленькие слагаемые дают много повторяющихся паттернов.

procedure FSP(N, K, Minn: Integer; Reslt: string);
var
  i: Integer;
begin
  if (K = 0) then begin
    if (N = 0) then
      Memo1.Lines.Add(Reslt); //yield result
    Exit;
  end;

  i := Minn;
  while (i * i <= N) do begin
    FSP(N - i * i, K - 1, i, Reslt + Format('%d ', [i]));
    i := i + 1;
  end;
end;

procedure FindSquarePartitions(N, K: integer);
begin
  FSP(N, K, 1, '');
end;

 FindSquarePartitions(101, 5);

1 1 1 7 7 
1 1 3 3 9 
1 1 5 5 7 
1 2 4 4 8 
1 5 5 5 5 
2 2 2 5 8 
2 3 4 6 6 
2 4 4 4 7 
3 3 3 5 7