Efficient algorithm to generate all solutions of a linear diophantine equation with ai=1
- by Ben
I am trying to generate all the solutions for the following equations for a given H.
With H=4 :
1) ALL solutions for x_1 + x_2 + x_3 + x_4 =4
2) ALL solutions for x_1 + x_2 + x_3 = 4
3) ALL solutions for x_1 + x_2 = 4
4) ALL solutions for x_1 =4
For my problem, there are always 4 equations to solve (independently from the others). There are a total of 2^(H-1) solutions. For the previous one, here are the solutions :
1) 1 1 1 1
2) 1 1 2 and 1 2 1 and 2 1 1
3) 1 3 and 3 1 and 2 2
4) 4
Here is an R algorithm which solve the problem.
library(gtools)
H<-4
solutions<-NULL
for(i in seq(H))
{
res<-permutations(H-i+1,i,repeats.allowed=T)
resum<-apply(res,1,sum)
id<-which(resum==H)
print(paste("solutions with ",i," variables",sep=""))
print(res[id,])
}
However, this algorithm makes more calculations than needed. I am sure it is possible to go faster. By that, I mean not generating the permutations for which the sums is H
Any idea of a better algorithm for a given H ?
