An efficient algorithm for generating all solutions of a linear Diophantine equation with ai = 1

Question

I am trying to generate all the solutions for the following equations for a given H.

When 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 (independent of others). There are only 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 the R algorithm that solves 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 does more calculations than necessary. I'm sure you can go faster. By this, I mean not to generate permutations for which the sums> H

Any idea of ​​a better algorithm for a given H?

Answer 1

Here's the implementation in C ++

blah.cpp:

 #include <stdlib.h> #include <iostream> #include <vector> using namespace std; vector<int> ilist; void diophantine(int n) { size_t i; if (n==0) { for (i=0; i < ilist.size(); i++) cout << " " << ilist[i]; cout << endl; } else { for (i=n; i > 0; i--) { ilist.push_back(i); diophantine(ni); ilist.pop_back(); } } } int main(int argc, char** argv) { int n; if (argc == 2 && (n=strtol(argv[1], NULL, 10))) { diophantine(n); } else cout << "usage: " << argv[0] << " <Z+>" << endl; return 0; } 

command line stuff:

 $ g++ -oblah blah.cpp $ ./blah 4 4 3 1 2 2 2 1 1 1 3 1 2 1 1 1 2 1 1 1 1 $ 

Here's the implementation in bash :

blah.sh:

 #!/bin/bash diophantine() { local i local n=$1 [[ ${n} -eq 0 ]] && echo "${ilist[@]}" || { for ((i = n; i > 0; i--)) do ilist[${#ilist[@]}]=${i} diophantine $((ni)) unset ilist[${#ilist[@]}-1] done } } RE_POS_INTEGER="^[1-9]+$" [[ $# -ne 1 || ! $1 =~ $RE_POS_INTEGER ]] && echo "usage: $(basename $0) <Z+>" || { declare -a ilist= diophantine $1 } exit 0 

Here's the implementation in Python

blah.py:

 #!/usr/bin/python import time import sys def output(l): if isinstance(l,tuple): map(output,l) else: print l, #more boring faster way ----------------------- def diophantine_f(ilist,n): if n == 0: output(ilist) print else: for i in xrange(n,0,-1): diophantine_f((ilist,i), ni) #crazy fully recursive way -------------------- def diophantine(ilist,n,i): if n == 0: output(ilist) print elif i > 0: diophantine(ilist, n, diophantine((ilist,i), ni, ni)) return 0 if len(ilist) == 0 else ilist[-1]-1 ########################## #main ########################## try: if len(sys.argv) == 1: x=int(raw_input()) elif len(sys.argv) == 2: x=int(sys.argv[1]) else: raise ValueError if x < 1: raise ValueError print "\n" #diophantine((),x,x) diophantine_f((),x) print "\nelapsed: ", time.clock() except ValueError: print "usage: ", sys.argv[0], " <Z+>" exit(1) 

Answer 2

As with many problems, a solution becomes much easier to find / research when any terminology is known.

Solutions to these problems are known as Integer Compositions , which in the long run are a generalization of Integer sections (where the order does not matter, i.e. only the answers that are the only ones in the permutation).

For example, whole sections 4 are equal: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, 4, while whole compositions 4 are equal: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 1 + 3, 3 + 1, 2 + 2, 4.

There are several implementations available (links to language agnostic algorithms follow):

• Since you are working in R , partitions can generate partitions for you. You will need to find unique permutations for each section in order to get compositions (see this SO question ).
• If you can use another language (either by interacting with R or by pre-computing the answer), then Mathematica has a function to calculate compositions: Compositions .
• Sage is free (unlike Mathematica), and also has the function of generating built compositions: Compositions . It is worth noting that this is implemented using generators that can use memory more efficiently.
• Python : see this Question (which generates sections that you can then rearrange). I did something similar here (although it uses itertools to find permutations, which I then need to filter for unique permutations, so that it can be more efficient using a permutation algorithm specifically for multisets).

To better understand the algorithms (or implement them yourself), you can check out this incomplete but useful e-book: Combinatorial Generation Frank Ruskey , which shows how to generate sections in constant depreciation time (CAT). Since you want to create compositions, you can also use the CAT algorithm to generate permutations (also in the book) to generate permutations of each integer section.

Ruskey also explains how to rank and expand them, which can be convenient for storing / hashing the results.

I find that they are also well covered in Knuth Art of Computer Programming Volume 4A, if that suits you.

ElKamina's suggestion for its recursive solution is good, but I would not use this approach for large H; since R (as well as Python) does not optimize tail-calls , you can end the stack overflow.

Answer 3

I assume that you are not trying to solve the equations at the same time.

You can use recursion or dynamic programming to solve this problem.

If you use recursion, just assign a real value to the first variable and solve it recursively.

Here n is the number of variables, and sum is the sum. cursol is a partial solution (originally set to [])

 def recSolve(n,sum, cursol): if n==1: print cursol + [sum] return if n == sum: print cursol + [1 for i in range(n)] return else: for i in range(1, sum-n+2): recsolve(n-1, sum-i, cursol+[i]) 

If you want to use dynamic programming, you need to remember the set of solutions for each combination of n and sum.