Dec 292017

Tiny SNOBOL program to print all permutations of characters in a string, with tutorial documentation. REVISED VERSION 10-3-92. | |||
---|---|---|---|

File Name | File Size | Zip Size | Zip Type |

PERMUTE.SNO | 1502 | 636 | deflated |

PERMUTE.TXT | 8309 | 3105 | deflated |

# Download File PERMUTE1.ZIP Here

## Contents of the PERMUTE.TXT file

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

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

December 29, 2017
Add comments