Introduction to Programming in ATS:
<<< PreviousEffectful Programming FeaturesNext >>>

Example: Ordering Permutations

Given a natural number n, we want to print out all the permutations consisting of integers ranging from 1 to n, inclusively. In addition, we want to print them out according to the lexicographic ordering on integer sequences. For instance, we want the following output to be generated when n is 3: 

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

Let us first define a function as follows for printing out an array of integers: 


fun print_intarray
  (A: array0 (int)): void = let
  val asz = array0_size (A) // get the size of the array
  val asz = int_of_size (asz) // turn [asz] to be of the type [int]
//
// The integers are to be separated by the string [sep]
//
  fun loop (i: int, sep: string):<cloref1> void =
    if i < asz then
      (if i > 0 then print sep; print A[i]; loop (i+1, sep))
    // end of [if]
in
  loop (0, ", ")
end // end of [print_intarray]

We next implement two functions lrotate and rrotate for rearranging the elements in a given integer array: 

fun lrotate (
  A: array0 int, i: int, j: int
) : void = let
  fun lshift (
    A: array0 int, i: int, j: int
  ) : void =
  if i < j then (A[i] := A[i+1]; lshift (A, i+1, j))
in
  if i < j then let
    val tmp = A[i] in lshift (A, i, j); A[j] := tmp
  end // end of [if]
end // end of [lrotate]

fun rrotate (
  A: array0 int, i: int, j: int
) : void = let
  fun rshift (
    A: array0 int, i: int, j: int
  ) : void =
  if i < j then (A[j] := A[j-1]; rshift (A, i, j-1))
in
  if i < j then let
    val tmp = A[j] in rshift (A, i, j); A[i] := tmp
  end // end of [if]
end // end of [rrotate]

When applied to an array and two valid indexes i and j for the array such that i is less than or equal to j, lrotate moves simultaneously the content of cell i into cell j and the content of cell k to cell k-1 for k ranging from i+1 to j, inclusively. The function rrotate is similar to lrotate but shuffles elements in the opposite direction.

Given a natural number n, the following defined function permute prints out all the permutations consisting of integers ranging from 1 to n, inclusively while arranging the output according to the lexicographic ordering on integer sequences. 

fun permute
  (n: int): void = let
//
  val asz = size_of_int (n)
  val A = array0_make_elt<int> (asz, 0)
//
// Initializing A with integers from 1 to n, inclusively
//
  val () = init (0) where {
    fun init (i: int):<cloref1> void =
      if i < n then (A[i] := i+1; init (i+1))
  } // end of [val]
//
  fun aux (
      i: int
    ) :<cloref1> void =
    if i <= n then aux2 (i, i) else (
      print_intarray (A); print_newline ()
    ) // end of [if]
  and aux2 (
      i: int, j: int
    ) :<cloref1> void =
    if j <= n then let
      val () = (
        rrotate (A, i-1, j-1); aux (i+1); lrotate (A, i-1, j-1)
      ) // end of [val]
    in
      aux2 (i, j+1)
    end // end of [if]
//
in
  aux (1)
end // end of [permute]

Note that where is a keyword, and the expression (exp where { decseq }) for some expression exp and declaration sequence decseq is equivalent to the let-expression of the form (let decseq in exp end). To understand the behavior of the function aux, let us evaluate aux(1) while assuming that n is 4 and the 4 elements of the array A are 1, 2, 3, and 4. It should be fairly straightforward to see that this evaluation leads to the evaluation of aux(2) for 4 times: the array A contains (1, 2, 3, 4) for the first time, and (2, 1, 3, 4) for the second time, and (3, 1, 2, 4) for the third time, and (4, 1, 2, 3) for the fourth time. With some inductive reasoning, it should not be difficult to see that evaluating aux(1) indeed leads to all the permutations being output according to the lexicographic ordering on integer sequences.

Please find the entire code in this section plus some additional code for testing on-line.

<<< PreviousHomeNext >>>
ArraysUpMatrices