Compute a list of distinct odd numbers (if one exists), such that their sum is equal to a given number

Question

:- use_module(library(clpfd)). % load constraint library

% [constraint] Compute a list of distinct odd numbers (if one exists), such that their sum is equal to a given number.

odd(Num) :- Num mod 2 #= 1.

sumOfList([],N,N) :- !.
sumOfList([H|T],Counter,N) :-
  NewN #= H + Counter,
  sumOfList(T,NewN,N).

buildOddList(N,InputList,L) :-
  %return list when sum of list is N
  V in 1..N,
  odd(V),
  append(InputList,[V],TempL),
  sumOfList(TempL,0,N)->
    L = TempL;
    buildOddList(N,TempL,L).

computeOddList(N) :-
  buildOddList(N,[],L),
  label(L).

This is my code, I can't seem to get the right output, any code critics? :)

And no, its me trying to learn constraint programming, got it from a textbook though. I'm getting just True. — nubela, Nov 23 '09 at 22:22
What is your query? Since you only get True something is probably wrong with it. — starblue, Nov 24 '09 at 07:21

repeat · Answer 1 · 2015-04-30T05:32:32.010

Here my take on this question, realized by a predicate nonNegInt_oddPosSummands/2 and an auxiliary predicate list_n_sum/3:

:- use_module(library(clpfd)).

list_n_sum([],_,0).
list_n_sum([Z|Zs],N,Sum) :-
    Z #>= 1,
    Z #=< N,
    Z mod 2 #= 1,
    Sum  #=  Z + Sum0,
    Sum0 #>= 0,
    list_n_sum(Zs,N,Sum0).

nonNegInt_oddPosSummands(N,List) :-
    length(_,N),
    list_n_sum(List,N,N),
    chain(List,#<),
    labeling([],List).

Now on to some queries!

First, "which lists can 19 be decomposed into?":

?- nonNegInt_oddPosSummands(19,Zs).
Zs = [19] ;
Zs = [1, 3, 15] ;
Zs = [1, 5, 13] ;
Zs = [1, 7, 11] ;
Zs = [3, 5, 11] ;
Zs = [3, 7, 9] ;
false.

Next, a more general query that does not terminate as the solution set is infinite. "Which positive integers N can be decomposed into Zs if Zs has a length of 2?"

?- Zs=[_,_], nonNegInt_oddPosSummands(N,Zs).
N = 4,  Zs = [1,3] ;
N = 6,  Zs = [1,5] ;
N = 8,  Zs = [1,7] ;
N = 8,  Zs = [3,5] ;
N = 10, Zs = [1,9] ...

Finally, the most general query. Like the one above it does not terminate, as the solution set is infinite. However, it fairly enumerates all decompositions and corresponding positive integers.

?- nonNegInt_oddPosSummands(N,Zs).
N = 0,  Zs = []      ;
N = 1,  Zs = [1]     ;
N = 3,  Zs = [3]     ;
N = 4,  Zs = [1,3]   ;
N = 5,  Zs = [5]     ;
N = 6,  Zs = [1,5]   ;
N = 7,  Zs = [7]     ;
N = 8,  Zs = [1,7]   ;
N = 8,  Zs = [3,5]   ;
N = 9,  Zs = [9]     ;
N = 9,  Zs = [1,3,5] ;
N = 10, Zs = [1,9] ...

score 1 · Accepted Answer · answered Nov 24 '09 at 01:54

Can suggest you this solution:

:- use_module(library(clpfd)).

all_odd([]) :-!.
all_odd([H | T]) :-
 H mod 2 #= 1,
 all_odd(T).

solve(N,L) :-
 N2 is floor(sqrt(N)),
 Len in 1..N2,
 label([Len]),

 length(L, Len),

 L ins 1..N,

 all_different(L),
 all_odd(L),

 sum(L,#=,N),

 label(L),

 % only show sorted sets
 sort(L,L).

Example:

?- solve(17,L).
L = [17] ;
L = [1, 3, 13] ;
L = [1, 5, 11] ;
L = [1, 7, 9] ;
L = [3, 5, 9] ;
false.

score 1 · Answer 3 · edited May 23 '17 at 12:06

I see others have posted complete solutions already. Still, your code can be made to wok with only two slight modifications:

computeOddList only tests whether such a list exists. To know which list matches the constraints, just return it. Thus:
```
computeOddList(N, L) :-
    ...
```
The list TempL may currently contain duplicates. Just place all_different(TempL) after append to fix that.

Now computeOddList will return at least one list of distinct odd numbers if it exists. Still, for e.g. computeOddList(17, L) it will not return all lists. I don't know clpFD myself, so other than suggesting you compare your code to Xonix' code I cannot really help you.

score 0 · Answer 4 · answered Nov 23 '09 at 22:34

:- use_module(library(clpfd)). % load constraint library

% [constraint] Compute a list of distinct odd numbers (if one exists), such that their sum is equal to a given number.

odd(Num) :- Num mod 2 #= 1.

sumOfList([],N,N) :- !.
sumOfList([H|T],Counter,N) :-
  NewN #= H + Counter,
  sumOfList(T,NewN,N).

oddList([]) :- !.
oddList([H|T]) :-
  odd(H),
  oddList(T).

computeOddList(N,L) :-
  (L = [];L=[_|_]),
  length(L,V),
  V in 1..N,
  L ins 1..N,
  all_different(L),
  oddList(L),
  sumOfList(L,0,N).

I managed to kinda solved it, however it doesn't end properly after it runs out of cases. Hmm.

Compute a list of distinct odd numbers (if one exists), such that their sum is equal to a given number

4 Answers4

Linked