MODULE prog4;
(* This program displays the permutations of a string
   in alphabetic order *)
IMPORT IO,Str;

TYPE StringType = ARRAY [0..9] OF CHAR;

PROCEDURE NextPerm(n:CARDINAL;
                   VAR s:StringType;
                   VAR wrap:BOOLEAN);
(* This procedure updates s to the next permutation of the
   first n characters of s. The sequence of permutations
   generated by successive calls is in 'dictionary' order.
   If s is the last string in the sequence, the first is
   returned. The boolean result wrap is used to indicate
   this event *)
VAR
  i:CARDINAL; (* s[i-1] is the most significant char changed *)
  j:CARDINAL; (* s[j] is the char to be swapped with s[i-1] *)
  tmp:CHAR;

BEGIN
  IF n = 0 THEN
    wrap := TRUE;
    RETURN;
  END;
  i := n - 1;
  LOOP
    IF i = 0 THEN
      wrap := TRUE;
      EXIT;
    END;
    IF s[i-1] < s[i] THEN
      j := n - 1;
      WHILE s[j] <= s[i-1] DO
        j := j - 1;
      END;
      tmp := s[j]; s[j] := s[i-1]; s[i-1] := tmp; (* swap *)
      wrap := FALSE;
      EXIT;
    END;
    i := i - 1;
  END;
  (* s[i]..s[n-1] are in reverse order, reversing them
     yields the minimum permutation we require *)
  j := n - 1;
  WHILE i < j DO
    tmp := s[j]; s[j] := s[i]; s[i] := tmp;
    i := i + 1;
    j := j - 1;
  END;
END NextPerm;

VAR InputString:StringType;
    wrap:BOOLEAN;
    online:CARDINAL; (* number of strings in output line *)
    len:CARDINAL;
BEGIN
  IO.WrStr('Enter string : ');
  IO.RdStr(InputString);

  len := Str.Length(InputString);
  REPEAT
    NextPerm(len,InputString,wrap);
  UNTIL wrap;

  online := 0;
  REPEAT
    IO.WrStr(InputString);
    IO.WrStr('  ');
    online := online + 1;
    IF online = 6 THEN
      IO.WrLn;
      online := 0;
    END;
    NextPerm(len,InputString,wrap);
  UNTIL wrap;
END prog4.