20060303a

1 files changed, 131 insertions, 0 deletions

diff --git a/appl/math/perms.b b/appl/math/perms.b
new file mode 100644
index 00000000..23c5e52b
--- /dev/null
+++ b/appl/math/perms.b
@@ -0,0 +1,131 @@
+#
+#	initially generated by c2l
+#
+
+implement Perms;
+
+include "draw.m";
+
+Perms: module
+{
+	init: fn(nil: ref Draw->Context, argl: list of string);
+};
+
+include "sys.m";
+	sys: Sys;
+
+init(nil: ref Draw->Context, argl: list of string)
+{
+	sys = load Sys Sys->PATH;
+	main(len argl, argl);
+}
+
+# 
+#  * generate permutations of N elements
+#  *	from ``On Programming, an interim report on the SETL project'',
+#  *	Jacob T Schwartz (ed), New York University
+#  
+Seq: adt{
+	nel: int;
+	el: array of int;
+};
+
+origin: int = 1;
+
+main(argc: int, argv: list of string): int
+{
+	n: int;
+
+	if(argc > 1 && (as := hd tl argv)[0] == '-'){
+		origin = int (as[1: ]);
+		argc--;
+		argv = tl argv;
+	}
+	if(argc != 2){
+		sys->fprint(sys->fildes(2), "Usage: perms #elements\n");
+		exit;
+	}
+	n = int hd tl argv;
+	if(n > 0)
+		perms(n);
+	exit;
+}
+
+
+perms(n: int)
+{
+	seq: ref Seq;
+
+	seq = newseq(n);
+	do
+		putseq(seq);
+	while(eperm(seq) != nil);
+}
+
+putseq(seq: ref Seq)
+{
+	k: int;
+
+	for(k = 0; k < seq.nel; k++)
+		sys->print(" %d", seq.el[k]+origin);
+	sys->print("\n");
+}
+
+eperm(seq: ref Seq): ref Seq
+{
+	j, k, n: int;
+
+	n = seq.nel;
+	#  if sequence is monotone decreasing, there are no more
+	# 		permutations.  Otherwise, find last point of increase 
+	hit := 0;
+	for(j = n-2; j >= 0; j--)
+		if(seq.el[j] < seq.el[j+1]){
+			hit = 1;
+			break;
+		}
+	if(!hit)
+		return nil;
+	#  then find the last seq[k] which exceeds seq[j] and swop 
+	for(k = seq.nel-1; k > j; k--)
+		if(seq.el[k] > seq.el[j]){
+			{
+				t: int;
+
+				t = seq.el[k];
+				seq.el[k] = seq.el[j];
+				seq.el[j] = t;
+			}
+			;
+			break;
+		}
+	#  then re-arrange all the elements from seq[j+1] into
+	# 		increasing order 
+	for(k = j+1; k < (n+j+1)/2; k++){
+		kk: int;
+
+		kk = n-k+j;
+		{
+			t: int;
+
+			t = seq.el[k];
+			seq.el[k] = seq.el[kk];
+			seq.el[kk] = t;
+		}
+		;
+	}
+	return seq;
+}
+
+newseq(n: int): ref Seq
+{
+	seq: ref Seq;
+	k: int;
+
+	seq = ref Seq;
+	seq.nel = n;
+	seq.el = array[n] of int;
+	for(k = 0; k < n; k++)
+		seq.el[k] = k;
+	return seq;
+}