SNOBOL Permutation Algorithm


Here's a tutorial discussion of PERMUTE.SNO, a SNOBOL4 program
which generates all permutations of a string of characters. It
starts with a description of the fundamental algorithm, then
describes how the program implements that algorithm. Lines of
actual code are interspersed throughout the description, along with
specific discussion of those lines of code. The entire program is
then listed, and the discussion concludes with some comments as to
SNOBOL's suitability for this type application.


DESCRIPTION OF THE FUNDAMENTAL ALGORITHM

Given the string S consisting of characters C(1) . . . C(n), n>0:

For n>1, then the permutations of S can be represented by
those which begin with C(1) and conclude with the permutations of
the remaining characters of S, plus those which begin with C(2) and
conclude with the permutations of C(1), C(3) . . . C(n), and so on
through those which begin with C(n) and conclude with the
permutations of C(1) . . . C(n-1).

If n=1, then the permutations of S are simply C(1). This
relation terminates the recursion.

In general, the algorithm can be stated as, "Permutations of S
equal C(i) followed by permutations of the characters of S which
are not in position i, for all values of i. To terminate the
recursive definition, the permutations of a single character are
just that character."



IMPLEMENTATION OF THE ALGORITHM

The SNOBOL function PERMUTE(ARG,RESULT) implements this definition.
Originally called with just the first argument, ARG, it prints all
permutations of that argument. The function is declared to SNOBOL
as:

define('permute(arg,result)ch,pre,post')

[This declares ARG and RESULT as arguments and CH, PRE, and POST as
local variables. The value of an argument or a local variable in
SNOBOL is held as local to the current instantiation of the
function. Thus, PERMUTE can call itself recursively, and neither
the arguments nor the local variables interfere with the values of
their namesakes in lower level calls. Arguments in SNOBOL are
implicitly null if omitted, and a null value of the second
argument, RESULT, is the proper situation for the initial call.
RESULT is intended for internal use by the algorithm.]


PERMUTE begins by checking for an argument which is just one
character long. If this is the case, then the highest level of
recursion has been reached, and it's time to print the result and
fall back to a lower level. We'll defer looking at that line of
code till we've been through the loop a few times. It will be
clearer that way.

PERMUTE then enters a loop which breaks the original ARG string
into 3 pieces: the previous part (PRE), the character of current
interest (CH), and the remaining part (POST).

post = arg
loop:
post len(1) . ch rem . post :f(return)

[The first line of code copies ARG into POST, so that POST starts
out full. Then, within the loop, the first character is stripped
off POST and assigned to CH. This will continue with each pass
through the loop until there isn't any first character left, at
which point the function terminates and returns to the calling
function. (PRE doesn't feature in the program quite yet.)]


The previous part and the remaining part are concatenated and
comprise the first argument to the next higher level of recursion.
(In the definition of the algorithm, these together constitute
C(1) . . . C(n) except for C(i).) The character of current
interest (C(i) in the above definition) is concatenated to the
right end of the (initially null) partial result, which then is
also passed to the next level of recursion as its second argument.

permute(pre post, result ch)

[This line of code illustrates the recursive function call, with
concatenation happening within the function's two arguments. (A
space is SNOBOL's symbol for concatenation.) On the first
recursive call, PRE is null (because it hasn't yet received a
value) and POST is everything after the first character of the
argument. The first argument to the recursive call is therefore
just POST. RESULT is null and CH is C(1), so the second argument
to the recursive call is just the first character of ARG.]


ARG therefore becomes one character shorter at each level of
recursion, and RESULT become one character longer, until PERMUTE is
called with the ARG string down to just one character in length.
At that point, RESULT followed by the one-character ARG constitutes
a complete permutation. It is printed, and control drops from the
highest level of recursion to the level below.

output = eq(size(arg),1) result arg :s(return)

[This line illustrates SNOBOL's ability to condition execution of a
statement upon a test. If ARG is exactly 1 character long, then it
is concatenated onto the right end of RESULT, the concatenation is
displayed (assigned to OUTPUT), and the function returns. If ARG
is not 1 character long, the statement terminates at that point and
control drops through.]


At the return from the next higher level of recursion, the function
puts its current character onto the right end of its previous part
and takes the character from the left end of its remaining part to
become the character of current interest for the next pass through
the loop. Straightening out the loop, the execution of two passes
would look like:

permute(pre post, result ch)
pre = pre ch :(loop)
loop:
post len(1) . ch rem . post :f(return)
permute(pre post, result ch)

[This code puts CH onto the right end of PRE, then loops back to
try to strip the next character from the left end of POST. If
there isn't any next character, then POST has been emptied out and
the function has done its job -- at this level of recursion -- and
it's time to drop back to the calling function. If there is a
character to be taken from POST, then it goes into CH and the
function continues.]

This continues until the entire POST string has been processed and
no character remains to be assigned as the current character.
Recursion drops one level at that point, and the algorithm
continues until it finally drops out of the lowest level.



PROGRAM LISTING

Putting it all together, here is the entire algorithm, less
comments. See the full source code file, PERMUTE.SNO, for a fully
commented, operational version.

define('permute(arg,result)ch,pre,post')
. . .
permute
output = eq(size(arg),1) result arg :s(return)
post = arg
loop
post len(1) . ch rem . post :f(return)
permute(pre post, result ch)
pre = pre ch :(loop)



DISCUSSION

The power of SNOBOL in dealing with algorithms of this variety is
illustrated by the fact that the entire program, exclusive of the
function definition, labels, and test code, is implemented in only
5 lines of code. And I know at least one trick which could have
chopped another line from this total, at the expense of clarity. (I
didn't really need to use the variable POST. Since SNOBOL passes
arguments by value, I could have just used ARG in place of POST,
nibbling away at it by one character each time but not altering its
value in the lower level calling function. This would have saved
the POST = ARG line. But I don't think it's a good programming
practice to modify arguments within a function.)

Factors which influence this power include SNOBOL's ability to call
a function recursively, to maintain local variables within a
function, to condition operations on the results of logic tests
within the same line of code, and to handle uninitialized strings
as null, together of course with its essential capabilities of
pattern matching and concatenation. Note that the program didn't
need to do any counting or maintain any indexes. SNOBOL knows how
to do math, but counting is not its normal style of string scanning
or loop control.

SNOBOL does not execute quickly. That's the trade off.

The progam was executed on the excellent VANILLA SNOBOL4, available
on your nearby bulletin board.

Bruce B. Bottomley
Columbia, MD 21044
410 992-3908