| >I'm looking for
>a pascal permutation routine that will calculate all the permutations
>of a user's string input. (e.g. 'abc')
>any help would be greatly appreciated. I'm in desperate need of
>such a routine, or just the bare procedure.
If I remember correctly, there is a book 'Scientific Pascal' by Harley
Flanders that has a permutation generating program in it (although it
may be for numbers; it could probably be converted without difficulty).
The book used to be available in the DEC library at LTN 1.
michael
|
| This is an easy to solve problem using recursion...
IF the length of the string is 1,
THEN print it
ELSE
FOR each element of the string,
DO
print that element
Print the permutations of the string without that element
END
below lies sample pascal code...dont know how big a string it'll handle
before stack overflows....
-Robb
{ example of a recursive permutation routine }
Program Permutes(input,output);
TYPE
string=varying[120] of char;
VAR
line:STRING;
{ delete l places from starting at i }
FUNCTION sdelete(var S:string; i,l:integer):String;
BEGIN
IF length(s)>0
THEN IF i=1 { if delete from start }
THEN sdelete:=substr(s,i+l,length(s)-l)
ELSE sdelete:=substr(s,1,i-1)+substr(s,i+l,length(s)-(i+l-1));
END; {sdelete}
{ already is the `header' to the permutation, line is the line to `permute' }
PROCEDURE Permute(already,line:STRING);
VAR
i:INTEGER;
BEGIN
IF Length(line)=1
THEN writeLn(already,Line)
ELSE FOR i:=1 to Length(Line)
DO Permute(already+line[i],sdelete(line,i,1));
END;
BEGIN
Write('Enter line ');
readLn(line);
Permute('',line);
END.
|
| as a side note to -.1, this does not take into consideration duplicate
permutations...ie `ABA' will produce
ABA
AAB
BAA
BAA
AAB
ABA
you can either ignore this, or save all the permutation's into a list, tree,
hash-table, etc. That checks for duplicates before inserting. For reasonable
sized permutations this is probably the most efficient way to go.
-Robb
|
| Well, if you weren't so picky about the language... here's a structured
FORTRAN version of Nijenhuis and Wilf's Algorithm, from Combinatorial
Algorithms (Publ. 1975) that is very fast - shouldn't be too much trouble to
convert to PASCAL if you're that desperate. To use it, set MTC to 'true'
and
DO WHILE (mtc)
CALL nexper (size, index-vector, mtc)
etc.
It always computes the next permutation in the sequence by interchanging
just two elements, mostly just the 1st two, so it's minimum effort. The
integer vector is the index of the elements in the current permutation.
SUBROUTINE nexper (n, a, mtc)
C For an explanation of this algorithm, see Nijenhuis & Wilf,
C Combinatorial Algorithms, 1st Edition; Academic Press, 1975
IMPLICIT INTEGER (A-Z)
LOGICAL*1 mtc, odd
INTEGER a(n)
DATA nlast /0/
C======================================================================
IF (n .NE. nlast .OR. .NOT. mtc) THEN
C Initialization...
nlast = n
m = 1
odd = .true.
C Compute n!, and set up result vector.
nf = 1
DO j = 1, n
nf = nf * j
a(j) = j
END DO
mtc = (m .NE. nf)
RETURN
END IF
C
IF (odd) THEN ! Switch the first two indices
t = a(2)
a(2) = a(1)
a(1) = t
C
ELSE ! Figure out which two to switch...
h = 3
m1 = m/2
b = mod(m1,h)
DO WHILE (b .EQ. 0)
m1 = m1 / h
h = h + 1
b = mod(m1,h)
END DO
m1 = n
DO j = 1, h - 1
m2 = a(j) - a(h)
IF (m2 .LT. 0) m2 = m2 + n
IF (m2 .LT. m1) THEN
m1 = m2
j1 = j
END IF
END DO
t = a(h)
a(h) = a(j1)
a(j1) = t
END IF
odd = .NOT. odd
m = m + 1
mtc = (m .NE. nf)
RETURN
END
|