Решение и создание уравнения с переменными, проиндексированными заданным набором (Haskell)

Я хочу решить следующую проблему в Haskell:

Пусть n будет натуральным числом, а A = [d_1 , ..., d_r] будет набором положительных чисел.

Я хочу найти все положительные решения следующего уравнения:

n = Sum d_i^2 x_i.

Например, если n= 12 и набор A= [1,2,3]. Я хотел бы решить следующее уравнение над натуральными числами:

x+4y+9z=12.

Достаточно использовать следующий код:

[(x,y,z) | x<-[0..12], y<-[0..12], z<-[0..12], x+4*y+9*z==12]

Моя проблема в том, что если n не фиксировано, а также набор A не фиксирован. Я не знаю, как «создать» определенное количество переменных, индексированных набором A.


variables indexing haskell linear-equation
person Miguel Román    schedule 03.05.2016    source источник
comment
Вы ищете это [(x,y,z,n) |n<-[0..12], x<-[0..3], y<-[0..3], z<-[0..3], x+4*y+9*z==n ] или [(x,y,z,n) |n<-[0..12], x<-[0..n], y<-[0..n], z<-[0..n], x+4*y+9*z==n ] ?   -  person nobody    schedule 04.05.2016
comment
Мне нужно больше переменных. Количество переменных такое же, как мощность множества A. Если множество A равно A = [1, 2, 3, 4, 6]. Тогда уравнение будет таким: a+ 2b + 9c+ 16d+ 36e = n.   -  person Miguel Román    schedule 04.05.2016
comment
Насколько дальше вам нужна кардинальность?   -  person nobody    schedule 04.05.2016

Ответы (2)


arrow_upward
3
arrow_downward

Вместо понимания списка вы можете использовать рекурсивный вызов с do-нотацией для списка-монады.

Это немного сложнее, так как вам нужно правильно обрабатывать пограничные случаи, и я позволил себе немного оптимизировать:

solve :: Integer -> [Integer] -> [[Integer]]
solve 0 ds = [replicate (length ds) 0]
solve _ [] = []
solve n (d:ds) = do
  let maxN = floor $ fromIntegral n / fromIntegral (d^2)
  x <- [0..maxN]
  xs <- solve (n - x * d^2) ds
  return (x:xs)

это работает так:

  • Он отслеживает оставшуюся сумму в первом аргументе
  • когда эта сумма равна 0, где явно сделано и нужно вернуть только 0 (первый случай) - он вернет список 0 с той же длиной, что и ds
  • если оставшаяся сумма не 0, но не осталось d, у нас проблемы, так как решений нет (второй случай) - обратите внимание, что нет решений - это просто пустой список
  • in every other case we have a non-zero n (remaining sum) and some ds left (third case):
    • now look for the maximum number that you can pick for x (maxN) remember that x * d^2 should be <= n so the upper limit is n / d^2 but we are only interested in integers (so it's floor)
    • попробовать все от x от 0 до maxN
    • найдите все решения оставшейся суммы при использовании этого x с оставшимися ds и выберите одно из этих xs
    • объедините x с xs, чтобы получить решение текущей подзадачи

Связывание list-monad сделает все остальное за вас ;)

Примеры

λ> solve 12 [1,2,3]
[[0,3,0],[3,0,1],[4,2,0],[8,1,0],[12,0,0]]

λ> solve 37 [2,3,4,6]
[[3,1,1,0],[7,1,0,0]]

замечание

это не удастся при работе с отрицательными числами - если вам нужны те, которые вам нужно будет ввести еще несколько случаев - я уверен, что вы их разберетесь (на данный момент это действительно больше математики, чем Haskell)

person Random Dev    schedule 04.05.2016
comment
Мощность множества A вообще не меняется, и даже n остается фиксированным. - person nobody; 04.05.2016
comment
@nobody, вы должны прочитать вопрос: Моя проблема в том, что n не фиксировано, а также не фиксировано множество A. - person Random Dev; 04.05.2016
comment
Я имею в виду, что набор вашего решения A и «n» не меняются. - person nobody; 04.05.2016
comment
извините, я понятия не имею, о чем вы говорите - в двух примерах используются разные n и разные A - person Random Dev; 04.05.2016
comment
Автору нужно, чтобы набор A был набором базовой переменной, которую можно было бы изменить на квадрат, если я не ошибся в его идее. - person nobody; 04.05.2016
comment
снова - для n=12 и A=[1,2,3], который является одним из приведенных выше примеров OP, дает тот же результат, что и данное понимание [(x,y,z) | x<-[0..12], y<-[0..12], z<-[0..12], x+4*y+9*z==12] - и мне очень жаль, но я действительно не понимаю, какое здесь должно быть изменение на квадрат - person Random Dev; 04.05.2016
comment
его идея была довольно ясной - решить n = Sum d_i^2 x_i для заданных d_is и n для x_i и выше сделает именно это - результирующие списки будут x_i - вы можете проверить это: 2^2 * 3 + 3^2 * 1 + 4^2 * 1 + 6^2 * 0 = 37 что является решением для n=37 и A = [2,3,4,6] - person Random Dev; 04.05.2016
comment
кроме того, что он ошибочно принял 2 ^ 2 = 2 вместо 4, это именно то, что я здесь делаю - количество элементов результирующих списков будет таким же, как у A (где кардинальность - это просто длина списка) - person Random Dev; 04.05.2016
comment
единственная разница здесь заключается в том, что здесь созданные решения представлены списками, а не кортежами, чего следует ожидать, поскольку длина зависит от длины ввода, и вам потребуются тяжелые хиттеры (зависимые типы), чтобы получить кортежи с правильной длиной. этого - person Random Dev; 04.05.2016

arrow_upward
1
arrow_downward

Некоторые подсказки:

В конечном итоге вы хотите написать функцию с такой сигнатурой:

solutions :: Int -> [Int] -> [ [Int] ]

Примеры:

solutions 4 [1,2]  == [ [4,0], [0,1] ]
  -- two solutions: 4 = 4*1^2 + 0*2^2,  4 = 0*1^2 + 1*2^2

solutions 22 [2,3]  == [ [1,2] ]
  -- just one solution: 22 = 1*2^2 + 2*3^2

solutions 10 [2,3]  == [ ]
  -- no solutions

Шаг 2. Определите solutions рекурсивно на основе структуры списка:

solutions x [a] = ...
  -- This will either be [] or a single element list

solutions x (a:as) = ...
  -- Hint: you will use `solutions ... as` here
person ErikR    schedule 04.05.2016