Declaratieve Talen/oplossingenPalindromen

% Warning: Does not generate all solutions. % % Substitutes elements which occur the least in the list. % The cost is defined as the number of subsitutions, hence % the length of the list minus the times the most common element occurs. % Torben Gernaey & Sven Thijssen allesgelijk(List, Cost, Result) :-

   map_elements(List, UnsortedMap),
   sort(UnsortedMap, SortedLowToHighMap),
   reverse(SortedLowToHighMap, SortedHighToLowMap),
   most_common(SortedHighToLowMap, Times, Element),
   substitute(List, Element, Result),
   length(List, Length),
   Cost is Length - Times.
   

map_elements(List, Map) :-

   map_elements(List, [], Map).

map_elements([], Map, Map). map_elements([Element|List], Map, Result) :-

   \+ member(pair(_, Element), Map),
   append([pair(1, Element)], Map, NewMap),
   map_elements(List, NewMap, Result).

map_elements([Element|List], Map, Result) :-

   member(pair(_, Element), Map),
   update_element(Element, Map, [], NewMap),
   map_elements(List, NewMap, Result).

update_element(_, [], Result, Result). update_element(Element, [pair(Value, Key)|Map], Temp, Result) :-

   Element \= Key,
   update_element(Element, Map, [pair(Value, Key)|Temp], Result).

update_element(Element, [pair(Value, Element)|Map], Temp, Result) :-

   NewValue is Value + 1,
   update_element(Element, Map, [pair(NewValue, Element)|Temp], Result).

most_common([pair(Times,Element)|_], Times, Element). substitute([], _, []). % Not necessary to split, since all elements will be the same. % Other solution: % substitute([_|List], Element, [Element|Result]) :- % substitute(List, Element, Result). substitute([X|List], Element, [Element|Result]) :-

   X \= Element,
   substitute(List, Element, Result).

substitute([Element|List], Element, [Element|Result]) :-

   substitute(List, Element, Result).