1# 2# initially generated by c2l 3# 4 5implement Perms; 6 7include "draw.m"; 8 9Perms: module 10{ 11 init: fn(nil: ref Draw->Context, argl: list of string); 12}; 13 14include "sys.m"; 15 sys: Sys; 16 17init(nil: ref Draw->Context, argl: list of string) 18{ 19 sys = load Sys Sys->PATH; 20 main(len argl, argl); 21} 22 23# 24# * generate permutations of N elements 25# * from ``On Programming, an interim report on the SETL project'', 26# * Jacob T Schwartz (ed), New York University 27# 28Seq: adt{ 29 nel: int; 30 el: array of int; 31}; 32 33origin: int = 1; 34 35main(argc: int, argv: list of string): int 36{ 37 n: int; 38 39 if(argc > 1 && (as := hd tl argv)[0] == '-'){ 40 origin = int (as[1: ]); 41 argc--; 42 argv = tl argv; 43 } 44 if(argc != 2){ 45 sys->fprint(sys->fildes(2), "Usage: perms #elements\n"); 46 exit; 47 } 48 n = int hd tl argv; 49 if(n > 0) 50 perms(n); 51 exit; 52} 53 54 55perms(n: int) 56{ 57 seq: ref Seq; 58 59 seq = newseq(n); 60 do 61 putseq(seq); 62 while(eperm(seq) != nil); 63} 64 65putseq(seq: ref Seq) 66{ 67 k: int; 68 69 for(k = 0; k < seq.nel; k++) 70 sys->print(" %d", seq.el[k]+origin); 71 sys->print("\n"); 72} 73 74eperm(seq: ref Seq): ref Seq 75{ 76 j, k, n: int; 77 78 n = seq.nel; 79 # if sequence is monotone decreasing, there are no more 80 # permutations. Otherwise, find last point of increase 81 hit := 0; 82 for(j = n-2; j >= 0; j--) 83 if(seq.el[j] < seq.el[j+1]){ 84 hit = 1; 85 break; 86 } 87 if(!hit) 88 return nil; 89 # then find the last seq[k] which exceeds seq[j] and swop 90 for(k = seq.nel-1; k > j; k--) 91 if(seq.el[k] > seq.el[j]){ 92 { 93 t: int; 94 95 t = seq.el[k]; 96 seq.el[k] = seq.el[j]; 97 seq.el[j] = t; 98 } 99 ; 100 break; 101 } 102 # then re-arrange all the elements from seq[j+1] into 103 # increasing order 104 for(k = j+1; k < (n+j+1)/2; k++){ 105 kk: int; 106 107 kk = n-k+j; 108 { 109 t: int; 110 111 t = seq.el[k]; 112 seq.el[k] = seq.el[kk]; 113 seq.el[kk] = t; 114 } 115 ; 116 } 117 return seq; 118} 119 120newseq(n: int): ref Seq 121{ 122 seq: ref Seq; 123 k: int; 124 125 seq = ref Seq; 126 seq.nel = n; 127 seq.el = array[n] of int; 128 for(k = 0; k < n; k++) 129 seq.el[k] = k; 130 return seq; 131} 132