## DEV Community is a community of 606,099 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# What Decision Trees Are

A decision tree is a tree data structure that allows selecting from a list of options, then from more and more options until reaching a terminal node, preventing the need to painstakingly check each whole set of options.

The following algorithm takes a set of options and converts them into a decision tree. Following the algorithm are some examples.

# Some Prolog Code

sort(Options0,Options1),
string_to_list1(Options1,1,_,[],Options2),
maplist(append,[Options2],[Options2a]),

merge_lists_a([1],Options2a,[],
Options3a),
sort(Options3a,Options3),!.

string_to_list1([],N,N,Options,Options) :- !.
string_to_list1(Options1,N1,N2,Options2a,Options2b) :-
Options1=[B|Rest],
string_to_list2(B,B,N1,N3,Options2a,Options2c),
[Options2c]=Options2d,
string_to_list1(Rest,N3,N2,[],Options2e),
Options2d=[[[_,D1,D2]|D3]],
Options2f=[[[1,D1,D2]|D3]],
append(Options2f,Options2e,Options2b).

string_to_list2(B,B1,N1,N2,A1,A2) :-
string_concat(D,"",B),
string_length(D,1),
append(A1,[[N1,D,[-,B1]]],A2),
N2 is N1 + 1,!.
string_to_list2(A,B1,N1,N2,B,C) :-
string_concat(D,E,A),
string_length(D,1),
N3 is N1 + 1,
append(B,[[N1,D,N3]],F),
string_to_list2(E,B1,N3,N2,F,C).

merge_lists_a([],Options1,Options2,Options3) :-
append(Options1,Options2,Options3),!.
merge_lists_a(N1,Options1,Options2,
Options3) :-
N1=[M1|Ms],
% If all As lead to the same letter then merge them
findall(A,(member([M1,A,_N2],Options1)),A1),
sort(A1,A11),
merge_lists_a1(M1,A11,Options1,[],Options31,[],N21),
append(Options2,Options31,Options32),
append(Ms,N21,M21),
sort(M21,M2),
merge_lists_a(M2,Options32,[],Options3).

merge_lists_a1(_,[],Options1,Options2,Options3,N,N) :-
append(Options1,Options2,Options3),!.
merge_lists_a1(N1,A1,Options1,Options2,Options3,NA61,NA7) :-
A1=[A2|A3],
findall([N2,A5,N3],(member([N1,A2,N2],Options1),
member([N2,A5,N3],Options1)),A4),
findall([N1,A2,N2],(member([N1,A2,N2],Options1)),A6),
((merge_lists_a2(A4))->
(%% merge N1 A2 N..., change N... in other states
merge_lists_a3(A6,Options1,Options4),
findall(N2,(member([N1,A2,N2],Options4)),NA6));
(merge_lists_a3(A6,Options1,Options4),
findall(N2,(member([N1,A2,N2],Options4)),NA6)
)),
append(Options2,Options4,Options5),
append(NA61,NA6,NA62),
merge_lists_a1(N1,A3,Options5,[],Options3,NA62,NA7).

merge_lists_a2(A4) :-
A4=[[_N1,A,_N2]|A5],
merge_lists_a22(A,A5).
merge_lists_a22(_A,[]) :- !.
merge_lists_a22(A,A5) :-
A5=[[_N1,A,_N2]|A6],
merge_lists_a22(A,A6).

merge_lists_a3(A6,Options1,Options3) :-
A6=[[N1,A,N2]|A8],
delete(Options1,[N1,A,_],Options1a),
(append(Options1a,[[N1,A,N2]],Options1aa)),
merge_lists_a4(N2,A8,Options1aa,[],Options3).

% delete transition to be merged
merge_lists_a4(N2,[],Options1,Options2,Options3
) :-
append(Options1,Options2,Options3),!.
merge_lists_a4(N2,A8,Options1,Options2,Options3) :-
A8=[[N1,A,N3]|A9],
delete(Options1,[N1,A,N3],Options2aa),
merge_lists_a5(N2,N3,Options2aa,[],Options4,[],Options5),
findall(N4,(member([N4,
,_],Options4)),N41),
subtract1(Options5,N41,[],Options45),
append(Options2,Options45,Options245),
merge_lists_a4(N2,A9,Options245,[],
Options31),
append(Options31,Options4,Options3).

% point second in pair to changed first state
merge_lists_a5(_N2,_N3,[],Options1,Options1,Options2,Options2) :- !.
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
Options1=[[N3,A,N4]|A9],
delete(Options2,[N3,A,N4],Options2aa),
append(Options2aa,[[N2,A,N4]],Options2a),
merge_lists_a5(N2,N3,A9,Options2a,Options4,Options5,Options6).
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
Options1=[[N2,A,N4]|A9],
delete(Options2,[N3,A,N4],Options2aa),
append(Options2aa,[[N2,A,N4]],Options2a),
merge_lists_a5(N2,N3,A9,Options2a,Options4,Options5,Options6).
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
Options1=[[N31,A,N4]|A9],
not(N2=N31),
append(Options5,[[N31,A,N4]],Options5a),
merge_lists_a5(N2,N3,A9,Options2,Options4,Options5a,Options6).

subtract1([],N41,Options45,Options45) :- !.
subtract1(Options5,N41,Options451,Options45) :-
Options5=[[N42,
,_]|Options51],
member(N42,N41),
subtract1(Options51,N41,Options451,Options45).
subtract1(Options5,N41,Options451,Options45) :-
Options5=[[N42,A,B]|Options51],
not(member(N42,N41)),
append(Options451,[[N42,A,B]],Options452),
subtract1(Options51,N41,Options452,Options45).

# Examples

(Intermediate) DT1=[[1,"a",2],[2,"b",3],[3,"c",[-,"abc"]],[1,"a",5],[5,"b",6],[6,"d",[-,"abd"]]]

DT2=[[1,"a",2],[2,"b",3],[3,"c",[-,"abc"]],[3,"d",[-,"abd"]]]

This is self-explanatory.

(Intermediate) DT1=[[1,"a",2],[2,"a",3],[3,"a",[-,"aaa"]],[1,"a",5],[5,"a",6],[6,"b",[-,"aab"]],[1,"a",8],[8,"c",9],[9,"c",[-,"acc"]]]

DT2=[[1,"a",2],[2,"a",3],[2,"c",9],[3,"a",[-,"aaa"]],[3,"b",[-,"aab"]],[9,"c",[-,"acc"]]]

(Intermediate) DT1=[[1,"c",2],[2,"c",3],[3,"a",[-,"cca"]],[1,"c",5],[5,"c",6],[6,"b",[-,"ccb"]]]

DT2=[[1,"c",2],[2,"c",3],[3,"a",[-,"cca"]],[3,"b",[-,"ccb"]]]

(Intermediate) DT1=[[1,"a",2],[2,"c",3],[3,"c",[-,"acc"]],[1,"b",5],[5,"c",6],[6,"c",[-,"bcc"]]]

DT2=[[1,"a",2],[1,"b",5],[2,"c",3],[3,"c",[-,"acc"]],[5,"c",6],[6,"c",[-,"bcc"]]]

The c's stay separate here, although can't be merged because the terminal strings are different.

(Intermediate) DT1=[[1,"a",2],[2,"c",[-,"ac"]],[1,"b",4],[4,"c",[-,"bc"]]]

DT2=[[1,"a",2],[1,"b",4],[2,"c",[-,"ac"]],[4,"c",[-,"bc"]]]

(Intermediate) DT1=[[1,"a",2],[2,"q",3],[3,"a",[-,"aqa"]],[1,"a",5],[5,"w",6],[6,"x",[-,"awx"]],[1,"a",8],[8,"w",9],[9,"y",[-,"awy"]]]

DT2=[[1,"a",2],[2,"q",3],[2,"w",9],[3,"a",[-,"aqa"]],[9,"x",[-,"awx"]],[9,"y",[-,"awy"]]]