Permutations

Problem: given a string (eg "abcd") print all the permutations

Algorithm:

1. print all permutations that start with a,
2. then all that start with b
3. with c
4. with d

   Reword the algorithm:

   1. print all permutations that start with the letter in a given position of the string
   2. print all permutations of the string that start with the letter in the next position.
      • this is the same problem, so recursion comes in
      • it is a smaller version of the problem, in that the next position is closer to the end of the string.
      • eventually there will be no next position, so the recursion stops

   Use a counter to record where to permutate from

   Code:

           size: constant integer:=4;
           word: string(1..size);
   
           procedure swapchar(S: in out word;a,b:integer) is
              temp:character;
           begin
              temp:=S(a);
              S(a):=S(b);
              S(b):=temp;
           end swapchars;
   
           procedure permutate(S: in word; k:in integer) is
                	
           begin
               if (k=S'LAST) then
   	        put(S);
               else
                    for i in k..S'LAST do
                    swapchars(S,k,i);
                    permute(S,k+1);
               end if;
           	
           end permute;
   
   

   ---

   Previous topic | Next topic | Ada Home Page | Index

   ---

   c-lokan@adfa.oz.au / 23 Feb 96