/* 

  Best shuffle in Picat.

  From Rosetta Code
  http://rosettacode.org/wiki/Best_shuffle
  """
  Shuffle the characters of a string in such a way that as many of the character values 
  are in a different position as possible. Print the result as follows: original string, 
  shuffled string, (score). The score gives the number of positions whose character value 
  did not change.

  For example: tree, eetr, (0)

  A shuffle that produces a randomized result among the best choices is to be preferred. 
  A deterministic approach that produces the same sequence every time is acceptable as 
  an alternative.

  The words to test with are: abracadabra, seesaw, elk, grrrrrr, up, a 
  """ 

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
import cp.
% import apl_util.


main => go.

% using cp approach
go =>
  Words = ["abracadabra", 
           "seesaw", 
           "elk", 
           "grrrrrr", 
           "up", 
           "a",
           "kjellerstrand",
           "thisis asdasdsasdasdjsasdsaddgasjdgashdgasjdgasd_a_longerstring",
           "assadashjfgljhfgrakjafkljfjlktrwlkjhglkflkjslkflkslkslsgflksfgjfgslkhjsgflkhgfslkhjsgflkhsflkghjsgflhkjsfglkjhslfghjsflghjlskgjhsgfh",
           "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
           ], 
  foreach(Word in Words)
     Best=best_shuffle_cp(Word),
     println([word=Word,best=Best,diff=diff_word(Word, Best)])
  end,

  nl.


go2 =>
  Words = ["abracadabra", "seesaw", "elk", "grrrrrr", "up", "a"], 
  foreach(Word in Words)
     Best=best_shuffle(Word),
     println([word=Best, diff_word(Word, Best)])
  end,
  nl.

go3 =>
   Alpha = "abcdefghijklmnopqrstuvwxyz",
   foreach(Len in 2..50..502)
     rnd_select2(Alpha, Len, Word),
     Best=best_shuffle_cp(Word),
     println([len=Len,word=Word,best=Best,diff=diff_word(Word, Best)])
   end,
   nl.



%
% CP approach. Guarantee the optimal shuffle
% 
best_shuffle_cp(Word) = Best =>
  WordAlpha = Word.map(ord),
  WordAlphaNoDups = WordAlpha.remove_dups(),
  Occurrences = occurrences(WordAlpha),

  % decision variables
  Len = Word.length,
  WordC = new_list(Len),
  WordC :: WordAlphaNoDups,
  
  % constraints 
  foreach(V in WordAlphaNoDups) 
     count(V, WordC,#=, Occurrences.get(V))
  end,
  Z #= sum([WordC[I] #= WordAlpha[I] : I in 1..Len]),

  solve([$min(Z),split], WordC),

  Best = WordC.map(chr).



% This don't guarantee the optimal shuffle
% best_shuffle(Word) = Word => Word.length == 1.
best_shuffle(Word) = BestWord =>
  BestWord1 = "",
  BestDiff = Word.length+1,
  % NoDups = Word.remove_dups(),
  foreach(_I in 1..min(1000,factorial(Word.length)), BestDiff > 0)
     P = rand_perm(Word),
     Diff = diff_word(Word,P),
     % writeln([p=P,diff=Diff]),
     if Diff < BestDiff then
        BestDiff := Diff,
        BestWord1 := P
     end
  end,
  BestWord = BestWord1,
  println(bestWordafter=BestWord).


diff_word(W1,W2) = Diff =>
  Diff = sum([1 : I in 1..W1.length, W1[I]==W2[I]]).

  
rand_perm(Word) = Word, Word.length == 1 => true.
rand_perm(Word) = Perm => rand_perm(Word, Word.length, Perm).

rand_perm(_,0,R) ?=> R = [].
rand_perm(Xs,N,R) ?=> 
    R = [X|Zs],
    N > 0,
    L = length(Xs),
    I = 1+random2() mod L,
    remove_at(X,Xs,I,Ys),
    N1 = N - 1,
    rand_perm(Ys,N1,Zs).

remove_at(X,L,1,R) => L=[X|Xs], R=Xs.
remove_at(X,L,K,R) => L=[Y|Xs], R=[Y|Ys], K #> 1, K1 #= K - 1, remove_at(X,Xs,K1,Ys).

% random selection _with_ replacement
rnd_select2(L,N,R) =>
    R1 = [],
    Len = L.length,
    foreach(_I in 1..N)
       E = L[1+random2() mod Len],
       R1 := R1 ++ [E]
    end,
    R = R1.


occurrences(L) = Occ => 
  Occ = new_map(),
  foreach(E in L)
    Occ.put(E, Occ.get(E,0) + 1)
  end.


my_count(V,L,Rel,N) =>
  println($my_count(V,L,Rel,N)),
  sum([V #= E : E in L]) #= Count,
  call(Rel,Count,N).