Best shuffle: Difference between revisions

Content added Content deleted

Inline

@@ Line 196: / Line 196: @@
 a a (1)</pre>
+=={{header|Prolog}}==
+Works with SWI-Prolog
+<lang Prolog>:- dynamic score/2.
+best_shuffle :-
+	maplist(best_shuffle, ["abracadabra", "eesaw", "elk", "grrrrrr",
+			       	"up", "a"]).
+best_shuffle(Str) :-
+	retractall(score(_,_)),
+	length(Str, Len),
+	assert(score(Str, Len)),
+	calcule_min(Str, Len, Min),
+	repeat,
+	   shuffle(Str, Shuffled),
+	   maplist(comp, Str, Shuffled, Result),
+	   sumlist(Result, V),
+	   retract(score(Cur, VCur)),
+	   (  V < VCur -> assert(score(Shuffled, V)); assert(score(Cur, VCur))),
+	   V = Min,
+	retract(score(Cur, VCur)),
+	writef('%s : %s (%d)\n', [Str, Cur, VCur]).
+comp(C, C1, S):-
+	(   C = C1 -> S = 1; S = 0).
+% this code was written by P.Caboche and can be found here :
+% http://pcaboche.developpez.com/article/prolog/listes/?page=page_3#Lshuffle
+shuffle(List, Shuffled) :-
+  length(List, Len),
+  shuffle(Len, List, Shuffled).
+shuffle(0, [], []) :- !.
+shuffle(Len, List, [Elem|Tail]) :-
+  RandInd is random(Len),
+  nth0(RandInd, List, Elem),
+  select(Elem, List, Rest),
+  NewLen is Len - 1,
+  shuffle(NewLen, Rest, Tail).
+% letters are sorted out then packed
+% If a letter is more numerous than the rest
+% the min is the difference between the quantity of this letter and
+% the sum of the quantity of the other letters
+calcule_min(Str, Len, Min) :-
+	msort(Str, SS),
+	packList(SS, Lst),
+	sort(Lst, Lst1),
+	last(Lst1, [N, _]),
+	(   N * 2 > Len -> Min is 2 * N - Len; Min = 0).
+% almost the same code as in "run_length" page
+packList([],[]).
+packList([X],[[1,X]]) :- !.
+packList([X|Rest],[XRun|Packed]):-
+    run(X,Rest, XRun,RRest),
+    packList(RRest,Packed).
+run(Var,[],[1,Var],[]).
+run(Var,[Var|LRest],[N1, Var],RRest):-
+    run(Var,LRest,[N, Var],RRest),
+    N > 0,
+    N1 is N + 1.
+run(Var,[Other|RRest], [1,Var],[Other|RRest]):-
+     dif(Var,Other).
+</lang>
+output : <pre> ?- test.
+abracadabra : brabaracaad (0)
+eesaw : sweea (0)
+elk : kel (0)
+grrrrrr : rrrgrrr (5)
+up : pu (0)
+a : a (1)
+true .
+</pre>
 =={{header|REXX}}==
 <lang rexx>/*REXX program to find best shuffle (of a character string).            */