


In 1977 or 1978, I wrote a program for the Texas Instruments TI58 calculator and PC100 printer that generated all the permutations of a string up to 10 characters in length. For example, given the string, "ABCDEF", the program would generate all 720 permutations of the string, beginning with "ABCDEF" and ending with the string reversed:
ABCDEF ABCDFE ABCEDF ABCEFD . . . FEDCBA 720 
A unique aspect of the program—a calculator program, mind you—was that it implemented a recursive permutation algorithm, complete with a call stack of memory registers to hold the local variables of the deeply nested function calls.
I thought of writing an article about the program and submitting it to Byte magazine. At the time, Byte published articles on diverse hardware and software computing subjects, both lowlevel and highlevel, so an article on a recursive calculator program would not have been out of the question. I'm pretty sure I wrote the beginnings of an article and I remember typing up one page at work after hours on our IBM Selectric typewriter (yes!). On the other hand, my memory could be playing tricks on me.
In the early 2000s, I created a web page for the original program, laboriously typing in the code listing from an old PC100 roll of printer paper. In April 2016, I came across Pierre Houbert's TI58C EMULATOR for Windows (and Linux under Wine) and wondered if I could get my program working in it. The first time I ran the TI58C EMULATOR, I was stunned. The emulator is a beautiful work of art, both visually and in terms of the programming effort that has gone into it. You're presented with a seemingly fullsize picture of the calculator, working buttons, printer output, and optional displays of the currently loaded program(s) and memory registers. (There are also sound effects, which I didn't notice right away because I usually work with my speakers off.)
Here's a picture of the emulator window (click the image to see it fullsize). I ran my permutation program on my "TRY IT" example (see Setting Up and Running the Program), let it print out some permutations, stopped the program, and reloaded the program and memory registers. In other words, the image shows the program and memory registers prior to running the program, not in the actual inprogress state you would have seen when the program was stopped.
The TI58C EMULATOR doesn't simply emulate the TI58C calculator, it also adds
new capabilities: 990 program steps, 1000 memory registers, and a whole slew
of new and useful 2nd
Op
operations. (And even more
features, as I'm continually discovering!)
Getting back to my permutation program ... The only documentation I had for the program was that old PC100 code listing. I had no information on how to set up the calculator before running the program. So I went to work and reverseengineered the program, figuring out how it works and what the memory registers are used for. In the process, I was able to move/eliminate some replicated/redundant code. This freed up some program storage, allowing me to replace branches to absolute locations with branches to labels.
An unrelated story, but interesting I hope! We used slide rules in high school, but when I began college in Fall 1974 as an astronomy major, I wanted/needed a scientific calculator. From studying various calculator history webpages, it appears that the common choice at the time (August or September 1974) was between the HewlettPackard HP35 ($395) and the new Texas Instruments SR50 ($170). Both would have seemed exorbitantly expensive, so I opted for the cheaper Sinclair Scientific, a tiny, odd, scientific calculator which displayed numbers in 5+2digit scientific notation. The calculator was introduced in 1974 and its price must have dropped immediately from the original $140; I'm pretty sure I got mine for about $70, or at least less than $100. The Sinclair Scientific was not really practical, but I somehow managed to use it in my Physics Lab class; I dropped out of college a year later and the calculator went into a desk drawer. Now, here is what is interesting: Ken Shirrif's webpage, "Reversing Sinclair's amazing 1974 calculator hack  half the ROM of the HP35", gives a fascinating account of how Sinclair's engineer, Nigel Searle, programmed the TI 320step, 4arithmeticfunction calculator chip to compute scientific functions, more or often less accurately! The webpage also includes a web emulator for the calculator with a sidebyside display of the calculator and the 320step program. When you click on a key, you can see the program run, with each step dynamically highlighted as it is executed.
I learned to program on a Texas Instruments SR56 programmable calculator, with 100 program steps and 10 memory registers. More precisely, it was the first actual computer to which I had access and on which I could run programs. I was simultaneously gaining reading knowledge of BASIC, ALGOL 60, FORTRAN, and Intel's 8080 microprocessor architecture and assembly language—among other computing topics. (I learned ALGOL and FORTRAN from Daniel McCracken's slim books on those two languages; at some point, I also purchased and read his magnum opus, A Simplified Guide to Structured COBOL Programming.) In the late summer or early fall of 1977, a good friend of my brother's and mine, Bob Stone, took us to his office in the Sounding Rockets department at NASA's Goddard Space Flight Center, showed us a box of $200 militarized 8080 chips, and let me try out a BASIC program I had written on his Intel 8080 development system. (His group flew 8080based experiments on highaltitude weather balloons, sounding rockets being outoffashion at the time despite the name of their department.) Bob saved my BASIC program on a paper tape, which I still have!
When the TI58 came out in 1977, I "graduated" from the SR56 to the TI58's 240 program steps and 30 memory registers. In retrospect, I should have plunked down the extra money for a TI59 with its ability to save and load programs to and from magnetic cards. The TI58 would lose everything when you turned it off and reentering a lengthy program every time you turned the calculator on was not a fun task. Pierre Houbert had/has the later TI58C which retained its program(s) and memory registers between calculator sessions.
Some time after purchasing the TI58, I bought the PC100 printer. I'm not sure exactly when I wrote the permutation program, in 1977 or 1978. I do know I used it in early 1978, generating the 720 permutations of "GYORGY" for my computer science teaching assistant (whom I had previously gotten to know when we took a physics class together in 1974) and the 720 permutations of "JEANNE" as a Mother's Day gift for my mom (it was the thought that counted, I hope!). This might lead me to believe that I wrote the program in 1978. However, I got an MEK6800D2 Evaluation Kit in December 1977 (see "Farmer Brown on a 6800") and I took a beginning computer science course in Spring 1978, so it seems as if the calculator would have taken a back seat to the 6800 microcomputer and to my FORTRAN class . Perhaps not, though.
I reverseengineered enough of the calculator program to figure out what registers to set in order to run the program, but not enough to figure out the exact permutation algorithm. My attempts to do the latter were why I appear overly concerned above on the question of whether I wrote the program in 1977 or in 1978. In the fall of 1977, I applied for readmission to the University of Maryland, I was accepted, and I signed up to take the beginning computer science course, CMSC 100, in Spring 1978. In January, before the course started, I bought the CMSC 100 textbook and the CMSC 420 textbook, my beloved Horowitz and Sahni's Fundamentals of Data Structures (forgive the missing possessive, but I've always referred to the book as if "Horowitz and Sahni" were a single entity).
Now, if I'd written the program in 1978, I might have used Horowitz's and Sahni's permutation algorithm found in Chapter 1 (in the book's SPARKS language):
procedure PERM(A,k,n) if k = n then [print (A); return] B < A for i < k to n do call INTERCHANGE(A,k,i) call PERM(A,k + 1,n) A < B end end PERM
(Here's a C program, perm.c, that implements H&S's algorithm.) I proceeded on this assumption when trying to reverseengineer the program. You'll notice that I use variable names A, i, k, and N in the memory register descriptions and the code listing comments. In fact, the calculator program saves the local variables A, i, and k on the stack when making a recursive call, as it should. N's value is fixed on the very first call to PERM() in H&S's algorithm, so it's a global variable, R7, in my calculator program. We'll ignore B for now.
I also figured I'd changed the algorithm so that i and k
count down to zero instead of up to N. However, no matter
how I tweaked the loop counting in the C program's PERM()
function and the character subscripting in the INTERCHANGE()
function, I couldn't match the output of the calculator program. Finally,
it had escaped my notice before, but H&S's algorithm doesn't generate
the permutations in what I consider to be the "correct" order! For example,
the permutations of "abc" listed in the book are different than
what H&S's own algorithm actually generates:
Book's list of results  Algorithm's list of results 

abc  abc 
acb  acb 
bac  bac 
bca  bca 
cab  cba 
cba  cab 
In English, H&S's algorithm defines the permutations of a set of N characters as each character followed by the permutations of the remaining N1 characters. In their second example, the permutations of "abcd" consist of:
My preference (and the way my calculator program works) is that the initial sequence of the remaining characters be in the same order as the characters' appearance in the original permutation string, "abcd" in this case. H&S, however, simply swap the first character, 'a', of the original string and the new initial character to get the initial sequence of remaining characters. For example, swapping 'a' and 'c' in "abcd" gives 'c' followed by the permutations of "bad" instead of the desired "abd".
I don't remember magically fixing Horowitz's and Sahni's permutation algorithm to generate the permutations in the "right" order (and I wouldn't know where to begin to fix it now), so I think it is evident that I did not use H&S's algorithm. But where did I get my algorithm? I guess I'll keep trying to reverseengineer it. (I later implemented a TI58 program using a genuinely iterative permutation algorithm without a stack, much faster than the recursive algorithm, and I don't remember where I found that algorithm either.)
Note that the program generates all the permutations of a string and does
not prune any duplicates. For example, the 6character string
"TRY IT" has two T
s, which the program treats as essentially
different characters. Consequently, it will generate two instances of
"TRY IT": "T_{1}RY IT_{6}" and
"T_{6}RY IT_{1}". In fact, the program will print out
720 permutations of "TRY IT" (the expected number for a 6character string),
half of which (360) are duplicates because of the two T
s.
NOTE that all the files below (".t58", ".hlp", ".lst", and ".wri") are ASCII files with Windowsstyle carriagereturn/linefeed line endings; the TI58C EMULATOR won't load the files correctly if they have Unixstyle linefeed endings.
Files for Pierre Houbert's TI58C EMULATOR:
or, separately:
Simply load "permutations.t58", clicking the "with datas"
checkbox so the emulator will automatically load the ".wri" file.
The memory registers are preloaded for the "TRY IT" example described
below. After loading the program and memory registers in one operation,
go ahead and run
(R/S
)
the program!
Houbert's emulator can also load the program in Guillaume Tello's ".lst" file format:
First of all, attach the calculator to the printer, plug the printer in, and turn on the calculator and printer.
Next, configure the calculator for 240 programming locations and 30 memory registers:
3
2nd
Op
17
After entering the keystrokes above, an actual TI58 calculator would display "239.29" (locations 0239 and registers 029). (Pierre Houbert's TI58C EMULATOR has 990 programming locations and 1000 memory registers, so "989.999" is displayed no matter how you configure it.)
Press LRN
,
key in the entire program without mistakes (!),
and press LRN
again to exit program entry mode.
Clear all of the memory registers:
2nd CMs
It's already zero, but initialize the permutation count (R0) to zero:
CLR
STO
00
Initialize R6 to one less than the length of the permutation string and R7 to exactly the length of the string. (In short, R7 is the length of the string and R6 is one less.) For example, if your string is "TRY IT" (6 characters), you would enter the following:
5 STO 06
6 STO 07
Initialize the stack pointer (R8) to point to the top of the stack. The stack starts with memory register 9, so set R8 to 9:
9
STO
08
Store the character indices (19 and 0) on the top of the stack (R9). This value is an integer between 1 and 10 digits in length (depending on the length of the permutation string), "nnnnnnnnnn". An index determines which memory register (2029) holds that character's printing code.
To simplify the program, index 0 and memory register 20 have special meanings. If the string being permuted is less than 10 characters in length, index 0 always represents a space character and memory register 20 must contain the printer code (00) for the space character. (Consider a 3character string with indices 123; the program has to pack characters in groups of 5 for loading into the alphanumeric printer registers, so it treats 123 as a 5digit number with leading zeroes, 00123. Those zeroes will automatically insert the blank character code (00), retrieved from memory register 20, in the left two positions of the printer register.)
If the string is exactly 10 characters in length, you can use indices 09 and memory registers 2029 any way you please. (Because the groups of 5 are fully populated—no implicit leading zeroes—there's no necessity to reserve index 0. Come to think of it, I guess this is also true for strings of length 5 ...)
For example, "TRY IT" has 4 different characters plus the space. Indices 1
(memory register 21) through 4 (memory register 24) reference the printer
character codes for T
, R
, Y
, and
I
, respectively. (I chose indices 14 for simplicity, but
they're arbitrary as long as you enter the printer codes in the correct
memory registers 2029.) Key in the following six indices for "TRY IT"
(0 is the space between the words):
123041
STO
09
Lookup and store the printer codes corresponding to the indices in the permutation string. The PC100 alphanumeric character codes (decimal numbers, not octal!) from Guillaume Tello's Texas Instruments TI 58C/TI 59 page:
In the "TRY IT" example above, memory register 20 is always zero and memory
registers 2124 hold the printer character codes for T
,
R
, Y
, and I
, respectively (ignore
the parenthesized comments):
CLR STO 20
(blank)
37 STO 21
(T)
35 STO 22
(R)
45 STO 23
(Y)
24 STO 24
(I)
The program is now ready to run, so:
R/S
The printer should start printing out the permutations at irregular intervals:
TRY IT TRY TI TRYI T TRYIT TRYT I TRYTI TR YIT TR YTI . . . TI YRT 720 
Generating and printing the 720 permutations for a 6character string (such as "TRY IT") using an actual TI58 calculator and PC100 printer took six hours, if I remember correctly. Using Pierre Houbert's TI58C EMULATOR, the program completes in a speedy 15 minutes on my desktop and a blazingly fast 4½ minutes on my laptop—nice!
Register(s)  Usage 

0 
Total # of permutations printed. (Incremented
here after printing a string
permutation.)

1 
Temporary storage:

2 
Temporary storage:

3 
Temporary storage:

4 
Temporary storage: antilog (R6) = 10^{R6}; used to mask out
second swap character in A. (Computed here.)

5  Index in A of first character to be swapped?

6 
Index in A of second character to be swapped?

7 
The length (1≤N≤10) of the string being permuted.
This is a setup parameter which must be set prior to running the
program.

8 
Stack pointer (SP). *R8 points to the memory register containing the
current call "frame". Pushing a call frame on the stack increments
R8 and popping a frame decrements R8.

09  19 
The call stack, beginning with register 9 and growing upwards
(possibly to register 19). One call frame is stored per memory
register and is encoded as a number, "nnnnnnnnnn.ik", where the
ten integer digits (19 and 0) are the current configuration of
the permutation indices and the two fractional digits are the
values of local variables i and k, respectively. The very first
call frame, in register 9, is a setup parameter which must be set
prior to running the program; you only need to specify the indices
for the initial permutation string, "nnnnnnnnnn" (or fewer digits
for a shorter string).

20  29 
Print codes, one letter per memory register. Registers 2029 contain
the twodigit character codes for the characters corresponding to
indices 0, 1, 2, ..., 9 in the permutation string. The PC100
alphanumeric character codes (decimal numbers, not octal!) from
Guillaume Tello's
Texas Instruments TI 58C/TI 59 page:

Step  Opcode  Command  Comments 

000  29  CP  Clear the T register (CP's function in a program). 
001  43  RCL 06  
002  06  06  
003  22  INV  
004  77  GE B  if (R6 ≥ 0) then 
005  12  B  
006  42  STO 05  
007  05  05  
008  76  LBL A  Beginning of loop through end of loop? The value of R5 is in the display register on entering the loop and on each subsequent iteration. 
009  11  A  
010  32  X/T  R5>T 
011  43  RCL 06  
012  06  06  
013  67  EQ A'  if (R6 != R5) then 
014  16  A'  
015  22  INV  R4 = antilog(R6) = 10^{R6} 
016  28  LOG  
017  42  STO 04  
018  04  04  
019  73  RC* 08  
020  08  08  
021  55  /  
022  32  X/T  Exchange *R8 (X) and R5 (T). 
023  22  INV  R3 = antilog(R5) = 10^{R5} 
024  28  LOG  
025  42  STO 03  
026  03  03  
027  55  /  
028  01  1  
029  00  0  
030  95  =  
031  22  INV  
032  59  INT  
033  65  *  
034  01  1  
035  00  0  
036  95  =  
037  59  INT  
038  42  STO 02  
039  02  02  
040  94  +/  
041  42  STO 01  
042  01  01  
043  32  X/T  R1>T 
044  55  /  
045  43  RCL 04  
046  04  04  
047  55  /  
048  01  1  
049  00  0  
050  95  =  
051  22  INV  
052  59  INT  
053  65  *  
054  01  1  
055  00  0  
056  95  =  
057  59  INT  
058  44  SUM 01  
059  01  01  
060  22  INV  
061  44  SUM 02  
062  02  02  
063  43  RCL 01  
064  01  01  
065  65  *  
066  43  RCL 03  
067  03  03  
068  95  =  
069  74  SM* 08  
070  08  08  
071  43  RCL 02  
072  02  02  
073  65  *  
074  43  RCL 04  
075  04  04  
076  95  =  
077  74  SM* 08  
078  08  08  
079  43  RCL 06  
080  06  06  endif (R6 != R5) 
081  76  LBL A'  (from 015) Begin encoding new stack frame (using R6?). 
082  16  A'  
083  55  /  
084  01  1  
085  00  0  
086  00  0  
087  85  +  
088  43  RCL 05  
089  05  05  
090  55  /  
091  01  1  
092  00  0  
093  85  +  
094  73  RC* 08  
095  08  08  
096  59  INT  
097  95  =  
098  72  ST* 08  Push the new frame onto the stack 
099  08  08  
100  69  OP 28  Increment SP (R8) 
101  28  28  
102  72  ST* 08  
103  08  08  
104  69  OP 36  Decrement R6 
105  36  36  
106  81  RST  endif (recursive call to permutation function) 
Print String  prints the current
permutation string. The printer can print a 20characterwide line
using the printer codes loaded into the four 5character registers
spanning the line. Since the program only prints out strings up
to 10 characters in length, the program only uses the center two
registers, #2 and #3, leaving the far left and right registers, #1
and #4, blank. The permutation string of 10 characters or less is
thus printed rightjustified in the central 10character span of
the line.


107  76  LBL B  (from 004) 
108  12  B  
109  73  RC* 08  Retrieve the character indices for the current permutation string. 
110  08  08  
111  55  /  Shift the rightmost 5 indices (with leading zeroes if N<5) to the right of the decimal point and store the result in R1. For example, if the current indices for a 7character string were 1234567, then 0.34567 would be stored in R1. 
112  05  5  
113  22  INV  
114  28  LOG  
115  95  =  
116  42  STO 01  
117  01  01  
118  59  INT  Take the next 5 indices to the left, shift them (with leading zeroes if N<10) to the right of the decimal point, and store the result in R2. For example, if the current indices for a 7character string were 1234567, then 0.00012 would be stored in R2. 
119  22  INV  
120  44  SUM 01  
121  01  01  
122  55  /  
123  05  5  
124  22  INV  
125  28  LOG  
126  95  =  
127  42  STO 02  
128  02  02  
129  69  OP 00  Clear printer's alphanumeric registers for entire line. 
130  00  00  
131  43  RCL 07  Full length N of string. If N>5, then load the leftmost N5 characters into printer register #2, the remaining 5 characters into register #3, and then print the string. If N≤5, then load the characters into printer register #3 and print the string. 
132  07  07  
133  32  X/T  Exchange X and T. 
134  05  5  
135  77  GE B'  if (R7 > 5) then 
136  17  B'  
137  71  SBR D  call AssembleWord(R2) 
138  14  D  
139  69  OP 02  Load printer's alphanumeric register #2 (characters 610) with the leftmost N5 characters, rightjustified. 
140  02  02  endif (R7 > 5) 
141  76  LBL B'  
142  17  B'  
143  43  RCL 01  
144  01  01  
145  42  STO 02  
146  02  02  
147  71  SBR D  call AssembleWord(R2) 
148  14  D  
149  69  OP 03  Load printer's alphanumeric register #3 (characters 1115) with the rightmost 5 characters (or fewer if N<5), rightjustified. 
150  03  03  
151  69  OP 05  Print the alphanumeric registers (20 characters) 
152  05  05  
153  69  OP 20  Increment R0 (total # of permutations printed) 
154  20  20  
155  76  LBL C  
156  13  C  
157  43  RCL 08  
158  08  08  
159  32  X/T  Exchange X and T. 
160  09  9  
161  77  GE E  All permutations generated (SP≤9)? Exit the program. 
162  15  E  
163  69  OP 38  Not done. Decrement SP (R8) 
164  38  38  
165  73  RC* 08  Pop last stack frame (encoded in value): "<character indices>.<variables>". 
166  08  08  
167  22  INV  Begin extracting variables from encoded stack frame. 
168  59  INT  
169  65  *  
170  01  1  
171  00  0  
172  95  =  
173  42  STO 06  
174  06  06  
175  59  INT  
176  42  STO 05  
177  05  05  
178  22  INV  
179  44  SUM 06  
180  06  06  
181  01  1  
182  00  0  
183  49  PRD 06  
184  06  06  
185  29  CP  Clear the T register (CP's function in a program). 
186  69  OP 35  Decrement R5 
187  35  35  
188  43  RCL 05  
189  05  05  
190  77  GE A  End of loop 
191  11  A  
192  61  GTO C  
193  13  C  
proc AssembleWord (R2)  assembles
and returns the printer codes for 5 characters. The indices for the
5 characters are passed in through memory register R2 in the following
format: "0.nnnnn", where each digit is an index (minus 20) into memory
registers 2029 (which contain the corresponding character codes).
AssembleWord() returns the 5 twodigit characters codes in
the display register as a single 10digit number number that can be
deposited into the desired alphanumeric register of the printer.


194  76  LBL D  proc AssembleWord(R2) 
195  14  D  
196  25  CLR  
197  42  STO 03  Set the character code accumulator (R3) to 0. 
198  03  03  
199  05  5  
200  42  STO 05  R5 = 5 (always pack assemble 5 characters) 
201  05  05  
202  76  LBL D'  loop for R5 = 5 to 1 
203  19  D'  
204  01  1  
205  00  0  
206  00  0  
207  49  PRD 03  Shift the character code accumulator (R3) two digits to the left (multiply by 100) so the next character code can be added. 
208  03  03  
209  01  1  
210  00  0  
211  49  PRD 02  Expose the next character index in R2 (multiply by 10); e.g., 0.31416 * 10 = 3.1416, thus bringing out the index, 3, of the first character. 
212  02  02  
213  02  2  
214  00  0  
215  44  SUM 02  R2 = R2 + 20 
216  02  02  
Recall Printer Code  recalls
the current character's printer code indirectly via R2. R2 contains
a value, "2n.nnn", where the digit to the left of the decimal point
is the current character's index into registers 2029 and the digits
to the right of the decimal point are characters still to be processed.
A real TI58 calculator only uses the integer portion of a memory
register's contents when performing an indirect address through the
register. However, the TI58C EMULATOR rounds
the register's contents up or down to the nearest integer. For
example, if R2 is 24.567, then "RC* 02" on a real TI58 will retrieve
the contents of R24, while the TI58C EMULATOR will round 24.567 up to
25 and retrieve the contents of R25. Until this is corrected, a
temporary fix is to replace the following two program locations,
"RC* 02", with "RCL 02 INT STO 04 RC* 04". (The emulator allows
the program to grow larger than 240 locations.)


217  73  RC* 02  Retrieve the character code from memory register 20+index; e.g., if R2 contains 3.1416, get the character code from memory register 23. 
218  02  02  
219  44  SUM 03  Insert the twodigit character code in the two leastsignificant digits of the accumulator (R3). 
220  03  03  
221  43  RCL 02  
222  02  02  
223  59  INT  
224  22  INV  
225  44  SUM 02  R2 = R2  int (R2) (Remove the justprocessed index from R2; e.g. 3.1416 becomes 0.1416.) 
226  02  02  
227  97  DSZ 05 D'  end loop (for R5 = 5 to 1) 
228  05  05  
229  19  D'  
230  43  RCL 03  Return the fullyassembled 5character print codes in the display register (X). 
231  03  03  
232  92  RTN  endproc ; 
End of Program  prints out the total number of permutations
generated and stops the program.


233  76  LBL E  
234  15  E  
235  98  ADV  
236  43  RCL 00  Total number of permutations generated. 
237  00  00  
238  99  PRT  
239  91  R/S  Stop! 