/* 

  Sattolo_cycle (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Sattolo_cycle
  """
  The   Sattolo cycle   is an algorithm for randomly shuffling an array in 
  such a way that each element ends up in a new position.

  Task

  Implement the Sattolo cycle for an integer array (or, if possible, an array 
  of any type).

  Specification

  Given an array items with indices ranging from 0 to last, the algorithm can 
  be defined as follows (pseudo-code):

   for i from last downto 1 do:
    let j = random integer in range 0 <= j <leq
    swap items[i] with items[j]

  Notes:
 
  - It modifies the input array in-place. If that is unreasonable in your programming 
    language, you may amend the algorithm to return the shuffled items as a 
    new array instead.
  - The algorithm can also be amended to iterate from left to right, if that is 
    more convenient.
  - The only difference between this and the Knuth shuffle, is that j is chosen from 
    the range 0 <= j < i, rather than 0 ≤ j <= i. This is what ensures that every 
    element ends up in a new position, as long as there are at least two elements.

  Test cases
  Input array 	Possible output arrays
  [] 	[]
  [10] 	[10]
  [10, 20] 	[20, 10]
  [10, 20, 30] 	[20, 30, 10]
  [30, 10, 20]
  [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] 	39,916,800 possibilities. You'll know you have a correct one if it has the same elements as the input array, but none in their original place.
  """


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

*/

main => go.

go =>
  Tests = [[],
           [10],
           [10, 20],
           [10, 20, 30],
           [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22],
           "sattolo cycle"],
  foreach(L in Tests)
    println(original=L),
    sattolo_cycle(L),
    println(shuffled=L),
    nl
  end,
  nl,
  foreach(_ in 1..10)
    L = 1..10,
    sattolo_cycle(L),
    println(L)
  end,
  nl.


go2 =>
  L = 1..10_000,
  time(sattolo_cycle(L)),
  % println(L),
  nl.


sattolo_cycle(L) =>
  foreach(I in L.len..-1..2)
    swap(L,I,random(1,I-1))
  end.

% Swap position I <=> J in list L
% (inplace)
swap(L,I,J)  =>
  T = L[I],
  L[I] := L[J],
  L[J] := T.