1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
/* O(2^n) algorithm for finding all combinations of numbers in a list
* that total a specific number.
*
* Calling sequence: FindSum(total_IsNumber, l_IsList)
*
* It returns a list of lists, each list containing a group of elements
* that add up to the requested number.
*
* This algorithm can be speeded up a lot if the summation is only done
* for numbers (by separating out the positive and negative values),
* but this routine is shorter and also works for any object you care
* to throw at it that has an addition operator defined for it (matrices,
* vectors, complex numbers, polynoms, etc.).
*
* It is a nice example of a piece of code that does things the Prolog
* way. The result is accumulated in one argument, which is treated as
* a list of results.
*
* Example:
*
* In( 1 ) = FindSum(10,{2,3,4,5,6,7})
* Out( 1 ) = {{6,4},{7,3},{5,3,2}};
*
*/
/* Main entry point for FindSum. */
FindSum(_total, l_IsList) <--
[
Local(r);
r:={}; /* r will contain the results. */
FindSum(total, l,{},0,r); /* find the solution */
r; /* return the results */
];
/* this is an exact match: add the current sum to the results. */
10 # FindSum(_total, _l, _current, _total, _result) <-- DestructiveAppend(result, current);
/* All terms consumed. return results found. */
20 # FindSum(_total, {}, _current, _sum, _result) <-- True;
/* Try to find sums, starting from current term and sum. */
30 # FindSum(_total, _l, _current, _sum, _result) <--
[
Local(term);
/* New term that can be used for sum. */
term:=Head(l);
/* try to find a sum WITHOUT this term. */
FindSum(total, Tail(l), current, sum, result);
/* try to find a sum WITH this term. */
FindSum(total, Tail(l), term:current, sum+term, result);
];
|
