[Prev][Next][Index][Thread]

Re: Quick permutations

This runs in under 0.5 seconds on a 450Mhz, Pentium III.  If anyone
wants to improve the code, please go ahead.


/*
based on:
  Ammeraal, Leendert 1996, Algorithms and Data Structures in C++ (New
York, NY: John
  Wiley & Sons Ltd.), pp. 290-296
*/

define variable *perm-list* = #();

define method permut (k :: <integer>, n :: <integer>, nums :: <vector>)
=> ()
       /* when k > n we are done and should print */
       if (k <= n)
         for (i from k to n)
             //  each element i is promoted to the kth place while the
rest
             //  of the items from k to i - 1 are shifted to make room
with
             //  a ripple-shift operation.
           let tmp = nums[i];
           for (j from i above k by -1)
             nums[j] := nums[j - 1];
           end for;
           nums[k] := tmp;

           /* recurse on k + 1 to n */
           permut(k + 1, n, nums);

           for (j from k below i)
             nums[j] := nums[j + 1];
           end for;

           nums[i] := tmp;
         end for;
       else
         *perm-list* := add!(*perm-list*, copy-sequence(nums));
       end if;
end method;


define method main () => ()
  let array = vector("dummy", 1, 2, 3, 4, 5, 6, 7, 8);
  let perms = #f;
  let (seconds, milliseconds) = timing ()
                                  perms := permut(1, 8, array);
                                end;
  format-out("%d seconds %d milliseconds\n", seconds, milliseconds);
  format-out("number of permutations = %d\n", size(*perm-list*));
end method main;


begin
  main();
end;




Sent via Deja.com
http://www.deja.com/
Follow-Ups: References: