In 1977 or 1978, I wrote a program for the Texas Instruments TI-58 calculator and PC-100 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 low-level and high-level, 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 PC-100 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 full-size 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 full-size). 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 in-progress state you would have seen when the program was stopped.
The TI58C EMULATOR doesn't simply emulate the TI-58C calculator, it also adds
new capabilities: 990 program steps, 1000 memory registers, and a whole slew
of new and useful
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 PC-100 code listing. I had no information on how to set up the calculator before running the program. So I went to work and reverse-engineered 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 scientic calculator. From studying various calculator history webpages, it appears that the common choice at the time (August or September 1974) was between the Hewlett-Packard HP-35 ($395) and the new Texas Instruments SR-50 ($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+2-digit 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 HP-35", gives a fascinating account of how Sinclair's engineer, Nigel Searle, programmed the TI 320-step, 4-arithmetic-function calculator chip to compute scientific functions, more or often less accurately! The webpage also includes a web emulator for the calculator with a side-by-side display of the calculator and the 320-step 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 SR-56 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 8080-based experiments on high-altitude weather balloons, sounding rockets being out-of-fashion at the time despite the name of their department.) Bob saved my BASIC program on a paper tape, which I still have!
When the TI-58 came out in 1977, I "graduated" from the SR-56 to the TI-58's 240 program steps and 30 memory registers. In retrospect, I should have plunked down the extra money for a TI-59 with its ability to save and load programs to and from magnetic cards. The TI-58 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 TI-58C which retained its program(s) and memory registers between calculator sessions.
Some time after purchasing the TI-58, I bought the PC-100 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 reverse-engineered 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 reverse-engineer 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
function and the character subscripting in the
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|
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 N-1 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 reverse-engineer it. (I later implemented a TI-58 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 6-character string
"TRY IT" has two
Ts, which the program treats as essentially
different characters. Consequently, it will generate two instances of
"TRY IT": "T1RY IT6" and
"T6RY IT1". In fact, the program will print out
720 permutations of "TRY IT" (the expected number for a 6-character string),
half of which (360) are duplicates because of the two
NOTE that all the files below (".t58", ".hlp", ".lst", and ".wri") are ASCII files with Windows-style carriage-return/line-feed line endings; the TI58C EMULATOR won't load the files correctly if they have Unix-style line-feed endings.
Files for Pierre Houbert's TI58C EMULATOR:
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
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 TI-58 calculator would display "239.29" (locations 0-239 and registers 0-29). (Pierre Houbert's TI58C EMULATOR has 990 programming locations and 1000 memory registers, so "989.999" is displayed no matter how you configure it.)
key in the entire program without mistakes (!),
again to exit program entry mode.
Clear all of the memory registers:
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 (1-9 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 (20-29) 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 3-character 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 5-digit 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 0-9 and memory registers 20-29 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
I, respectively. (I chose indices 1-4 for simplicity, but
they're arbitrary as long as you enter the printer codes in the correct
memory registers 20-29.) 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 PC-100 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 21-24 hold the printer character codes for
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:
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 6-character string (such as "TRY IT") using an actual TI-58 calculator and PC-100 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!
Total # of permutations printed. (Incremented here after printing a string permutation.)
Temporary storage: antilog (R6) = 10R6; used to mask out second swap character in A. (Computed here.)
Index in A of first character to be swapped?
Index in A of second character to be swapped?
The length (1≤N≤10) of the string being permuted. This is a setup parameter which must be set prior to running the program.
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 (1-9 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 20-29 contain the two-digit character codes for the characters corresponding to indices 0, 1, 2, ..., 9 in the permutation string. The PC-100 alphanumeric character codes (decimal numbers, not octal!) from Guillaume Tello's Texas Instruments TI 58C/TI 59 page:
|000||29||CP||Clear the T register (CP's function in a program).|
|004||77||GE B||if (R6 ≥ 0) then|
|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.|
|013||67||EQ A'||if (R6 != R5) then|
|015||22||INV||R4 = antilog(R6) = 10R6|
|022||32||X/T||Exchange *R8 (X) and R5 (T).|
|023||22||INV||R3 = antilog(R5) = 10R5|
|080||06||06||endif (R6 != R5)|
|081||76||LBL A'||(from 015) Begin encoding new stack frame (using R6?).|
|098||72||ST* 08||Push the new frame onto the stack|
|100||69||OP 28||Increment SP (R8)|
|104||69||OP 36||Decrement R6|
|106||81||RST||endif (recursive call to permutation function)|
Print String - prints the current permutation string. The printer can print a 20-character-wide line using the printer codes loaded into the four 5-character 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 right-justified in the central 10-character span of the line.
|107||76||LBL B||(from 004)|
|109||73||RC* 08||Retrieve the character indices for the current permutation string.|
|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 7-character string were 1234567, then 0.34567 would be stored in R1.|
|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 7-character string were 1234567, then 0.00012 would be stored in R2.|
|129||69||OP 00||Clear printer's alphanumeric registers for entire line.|
|131||43||RCL 07||Full length N of string. If N>5, then load the leftmost N-5 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.|
|133||32||X/T||Exchange X and T.|
|135||77||GE B'||if (R7 > 5) then|
|137||71||SBR D||call AssembleWord(R2)|
|139||69||OP 02||Load printer's alphanumeric register #2 (characters 6-10) with the leftmost N-5 characters, right-justified.|
|140||02||02||endif (R7 > 5)|
|147||71||SBR D||call AssembleWord(R2)|
|149||69||OP 03||Load printer's alphanumeric register #3 (characters 11-15) with the rightmost 5 characters (or fewer if N<5), right-justified.|
|151||69||OP 05||Print the alphanumeric registers (20 characters)|
|153||69||OP 20||Increment R0 (total # of permutations printed)|
|159||32||X/T||Exchange X and T.|
|161||77||GE E||All permutations generated (SP≤9)? Exit the program.|
|163||69||OP 38||Not done. Decrement SP (R8)|
|165||73||RC* 08||Pop last stack frame (encoded in value): "<character indices>.<variables>".|
|167||22||INV||Begin extracting variables from encoded stack frame.|
|185||29||CP||Clear the T register (CP's function in a program).|
|186||69||OP 35||Decrement R5|
|190||77||GE A||End of loop|
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 20-29 (which contain the corresponding character codes). AssembleWord() returns the 5 two-digit characters codes in the display register as a single 10-digit number number that can be deposited into the desired alphanumeric register of the printer.
|194||76||LBL D||proc AssembleWord(R2)|
|197||42||STO 03||Set the character code accumulator (R3) to 0.|
|200||42||STO 05||R5 = 5 (always pack assemble 5 characters)|
|202||76||LBL D'||loop for R5 = 5 to 1|
|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.|
|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.|
|215||44||SUM 02||R2 = R2 + 20|
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 20-29 and the digits to the right of the decimal point are characters still to be processed. A real TI-58 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 TI-58 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.|
|219||44||SUM 03||Insert the two-digit character code in the two least-significant digits of the accumulator (R3).|
|225||44||SUM 02||R2 = R2 - int (R2) (Remove the just-processed index from R2; e.g. 3.1416 becomes 0.1416.)|
|227||97||DSZ 05 D'||end loop (for R5 = 5 to 1)|
|230||43||RCL 03||Return the fully-assembled 5-character print codes in the display register (X).|
End of Program - prints out the total number of permutations generated and stops the program.
|236||43||RCL 00||Total number of permutations generated.|