Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Database

Algorithm Alley


JUN93: ALGORITHM ALLEY

This article contains the following executables: ALLEY.ARC

Flying with a computer is no fun anymore. I remember when just whipping out my laptop at 30,000 feet would cause all sorts of excitement. Now nobody notices--except, that is, when I playfully bring up an air-traffic control simulation, which almost guarantees a double take from the flight crew.

Not long ago, I was on an especially tedious flight--one of those that takes off and lands so many times you get the idea the pilot can't decide whether to fly the plane or drive it all the way to LA. The joker next to me wanted to talk; I didn't, so I buried my nose in the "complimentary magazine that I'm welcome to take with me."

That's when I saw an advertisement that led to this column. It listed a company's mnemonic telephone number, something like 1-800-555-BOAT. The mnemonic, of course, is supposed to help you remember the number by association.

Maybe that's true, but I always find these telephonic mnemonics hard to dial. So, having little else to do while the pilot perfected his landing technique, I decided to set up my laptop and write a program to generate the number for a telephone "name." But why stop there? I figured I could also write a program to output all possible names for any given number. The problem to solve was: What are all the possible words formed by a given telephone number? The solution took me back to my early programming days when I spent hours poking around with short but interesting algorithms known as permutations.

Permuting Computing

Permutation algorithms almost always use recursion, not because it's required (it never is), but because without it the algorithms are more difficult to understand. Example 1, Algorithm #2, shows one of the simplest permutation algorithms.

Example 1: Pseudocode for Algorithm #2 (Permutation One).

  procedure Permute(n: Integer);
  begin
   if n = 1 then Show array else
   begin
    Permute(n-1);
    for i <-- 1 to n-1 do
    begin
     Swap a[i] and a[n];
     Permute(n-1);
     Swap a[i] and a[n];
    end;
   end;
  end;

I found Algorithm #2 buried in an illustration in Niklaus Wirth's book, Algorithms+Data Structures=Programs. (Wirth doesn't explain the method.) The technique uses an array a of n integer values, initialized as a[1]=1, a[2]=2,..., a[n]=n. Passing n to Permute calls another procedure Show array for every possible combination of n values.

The algorithm works by making two recursive calls--unusual in recursive algorithms, which typically call themselves only once per recursion. On any level, if n equals 1, the procedure has reached the first array position and it displays the current permutation. Otherwise, a For loop works in the opposite direction, swapping pairs of values from 1 to n-1, and again calling Permute recursively for each iteration. The process resembles the way most people would permute an array of values manually.

Listing One (page 168) implements Algorithm #2 in Pascal. For a better understanding of how the algorithm works, set MAX to 3 and single-step the program in a debugger.

Example 2, Algorithm #3, shows a permutation method from Robert Sedgewick's book, Algorithms in C++ (Addison Wesley, 1992). The original algorithm uses an input array defined as array[O .. N]. My slightly modified version works with an array[1 .. N]. Listing Two (page 168) implements Algorithm #3. The method requires the input array to be initialized to all 0s. Essentially, the algorithm uses 0 as a flag that indicates more work to be done on each level of the recursion. Passing 1 to Permute causes the procedure to "visit" values from 1 to n as though they were nodes in a graph. In this sense, Algorithm #3 generates permutations by searching all paths to all nodes.

Example 2: Pseudocode for Algorithm #3 (Permutation Two).

  procedure Permute(n: Integer);
  begin
   pos <-- pos + 1;
   a[n] <-- pos;
   if pos = MAX then Show array;
   if pos <> MAX then
      for i <-- 1 to MAX do
       if a[i] = 0 then Permute(i);
   pos <-- pos-1;
   a[n] <-- 0;
  end;

The disadvantages of Algorithm #3 are the use of a unique flag value and the requirement that array values be integers. Algorithm #2 can permute any data, not only integers. The main advantage of Algorithm #3 is the single recursive call, which probably reduces stack use over Algorithm #2, although I haven't tested that assumption. So, what's all this got to do with telephones and chocolate? Patience, patience.

The Chocolate Coefficient

The permutations produced by Algorithms #2 and #3 solve the relatively simple problem of how to arrange a sequence in all possible ways. The count of these arrangements equals the factorial of the number of items. There are 24 ways to arrange the four-element sequence ABCD, and of course, the factorial of 4 is 24.

More complex permutations, such as telephone "names," require different techniques. In his delightful book, Innumeracy (Vintage, 1988), John Allen Paulos illustrates a similar proble with an ice-cream shop. Given 28 flavors, how many triple-decker ice-cream cones can the shop claim to offer?

The simple answer equals the number of possible ways to arrange 28 items in groups of threes, or 28*27*26. If you don't understand this, consider how many pairs of letters there are in the four-letter sequence ABCD. Disallowing duplicate pairs such as AA and BB, there are 12 (4*3) groups of two letters: AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, and DC. Likewise, there are 24 (4*3*2) combinations of three letters. If we could have 28 letters from which to choose, we could make 19,656 groups of three, or 28*27*26.

But wait a sec. If A is chocolate, B is vanilla, and C is strawberry, is it proper to consider cone ABC to be different from CBA? Probably not, unless you're the fussy type who insists on always having chocolate on top. What we really want is the number of unique ways to arrange 28 flavors in groups of three.

Deriving this value takes additional work. Given any set of three flavors A, B, and C, there are six possible permutations: ABC, ACB, BAC, BCA, CAB, and CBA. As just mentioned, this count equals the factorial of the number of items (6 is the factorial of 3). As ice-cream cones, all six combinations are equivalent, so the number of unique triple-deckers you can make from 28 flavors equals the number of nonunique combinations (19,656) divided by the factorial of 3, or 3276. This final value is called the "combinatorial coefficient." (If I ever open an ice-cream shop, I'll name it The Chocolate Coefficient. The first customer to guess the meaning of the name eats free.) Example 3, Algorithm #4, and Listing Three (page 168) put these ideas to the test. Run the program and enter 3, then 28 to compute the number of nonunique and unique combinations of three items selected from a set of 28.

Example 3: Pseudocode for Algorithm #4 (Combinatorial Coefficient).

  answer <-- elements;
  for i <-- 1 to selections-1 do
  begin
   elements <-- elements-1;
   answer <-- answer * elements;
  end;
  Write("Nonunique combinations = ",
                                    answer);
  answer <-- answer / Factorial(selections);
  WriteIn("Unique combinations = ", answer);

Telephonic Mnemonics

Unfortunately, none of the methods I've explained so far exactly solves the problem of generating all possible names for a given telephone number. In this case, we need a permutation technique that restricts letter groups to positions dictated by a telephone number. (Back at the ice-cream shop, you'd have a similar restriction if, say, you permitted the middle scoop to be only chocolate, vanilla, or strawberry.)

And there's another complication. Most, but not all, telephone digits are associated with three letters. The digit 2 is assigned ABC; 3 is given DEF, and so on. Digits 0 and 1 have no letters. Letters Q and Z are missing altogether. AT&T adopted this configuration in 1918 as a means of identifying the burgeoning list of directories. Digit 0 was reserved for quick access to the operator; digit 1, to signal another directory. Letters Q and Z, rarely used in directory names, were deleted to make the remaining 24 letters evenly divisible by the remaining eight numbers.

To keep the program simple, I pretend that digits 0 and 1 are represented by three spaces each. To associate letters and digits, I use an array of three-character strings indexed by telephone digits 0 to 9. Given that structure, it's easy to display the number for any telephone "name." Listing Four (page 168) shows the result. There's no corresponding algorithm because the program merely substitutes numbers for letters.

It's not as simple, however, to display all possible names for a given number. Example 4, Algorithm #5, shows the algorithm I used to solve this problem. As in the other permutation methods, this one relies on recursion to arrange a given set of letters in an output string.

Example 4: Pseudocode for Algorithm #5: Telephonic Mnemonic.

  procedure Permute(n: Integer);
  begin
   digit <-- ValueOfChar(inString[n]);
   for i <-- 1 to 3 do
   begin
    outString[n] <-- TelDial[digit][i];
    if (n = Length(inString)) then
     Write(outString)
    else
     Permute(n + 1);
   end;
  end;

Algorithm #5 uses an array TelDial of three-character strings. The expression TelDial[3] equals the string DEF. Treating this array as having two dimensions, a second subscript identifies a single letter. Thus TelDial[3][2] is the second letter in the string associated with the telephone digit 3--in this case, the letter E.

The method uses a For loop to set digit n in an output string to each of the possible letters for a given telephone digit. The procedure calls itself recursively for the next digit n+1, until reaching the end of the input string, at which point the code outputs the current permutation.

Listing Five (page 168) implements Algorithm #5 in a program that displays all possible names for any number. Enter your number or another to see what it can spell. (Telephone numbers with no 0s or 1s give the best results.)

The number of possible names for a single telephone number is not very large. Because there are only three letters per digit, a seven-digit number has only 3{7} or 2187 unique names (ignoring the problem of spaces for digits 0 and 1). A four-digit number generates only 3{4} or 81 names.

The total number of names for all possible numbers, however, is much more interesting. Using the formula for a combinatorial coefficient (hold the chocolate), all possible seven-digit telephone numbers have a whopping 1.7 billion permutations--that is, nonunique, seven-letter combinations of 24 letters. Adding a three-digit area code to the mix takes the total skyward toward the half-trillion mark. If there is a word that's not in there somewhere, I probably can't pronounce it anyway.

Your Turn

After entering your name or another phrase into Listing Four, try feeding the resulting number back into Listing Five to find all the other names your number-name can spell. For example, one of my telephonic-mnemonic aliases is VON-RYAN, which has a nice ring to it, don't you think? Perhaps there's some cryptographic value in these permutations, but for heaven's sake, don't use telephone number-names for online passwords.

Oh, the lengths I'll go to fight boredom at high altitudes.



_ALGORITHM ALLEY_
by Tom Swan


[LISTING ONE]
<a name="01a8_000d">

{ perm1.pas -- Algorithm #2: Permutation One by Tom Swan }
program Perm1;

const
  MAX = 4;

var
  i: Integer;
  a: array[1 .. MAX] of Integer;

{ Display contents of global array a }
procedure ShowArray;
var
  i: Integer;
begin
  for i := 1 to MAX do
    Write(a[i]:3);
  Writeln
end;

{ Arrange global array a in all possible ways }
procedure Permute(n: Integer);
var
  i, temp: Integer;
begin
  if n = 1 then ShowArray else
  begin
    Permute(n - 1);
    for i := 1 to n - 1 do
    begin
      temp := a[i];  { Swap a[i] and a[n] }
      a[i] := a[n];
      a[n] := temp;
      Permute(n - 1);
      temp := a[i];  { Restore a[i] and a[n] }
      a[i] := a[n];
      a[n] := temp
    end
  end
end;

begin
  for i := 1 to MAX do
    a[i] := i;
  Permute(MAX)
end.





<a name="01a8_000e">
<a name="01a8_000f">
[LISTING TWO]
<a name="01a8_000f">

{ perm2.pas -- Algorithm #3: Permutation Two by Tom Swan }
program Perm2;

const
  MAX = 4;

var
  pos: Integer;
  i: Integer;
  a: array[1 .. MAX] of Integer;

{ Display contents of global array a }
procedure ShowArray;
var
  i: Integer;
begin
  for i := 1 to MAX do
    Write(a[i]:3);
  Writeln
end;

{ Arrange global array a in all possible ways }
procedure Permute(n: Integer);
var
  i: Integer;
begin
  pos := pos + 1;
  a[n] := pos;
  if pos = MAX then ShowArray;
  if pos <> MAX then  { Optional }
    for i := 1 to MAX do
      if a[i] = 0 then Permute(i);
  pos := pos - 1;
  a[n] := 0
end;

begin
  pos := -1;
  for i := 1 to MAX do
    a[i] := 0;
  Permute(1)
end.






<a name="01a8_0010">
<a name="01a8_0011">
[LISTING THREE]
<a name="01a8_0011">

{ coco.pas -- Algorithm #5: Combinatorial Coefficient by Tom Swan }
program Coco;

var
  i: Integer;
  selections: Integer;
  elements: Integer;
  answer: Real;

function Factorial(n: Integer): Real;
var
  result: Real;
begin
  result := 1;
  while (n > 1) do
  begin
    result := result * n;
    n := n - 1
  end;
  Factorial := result
end;

begin
  Write('Number of selections? ');
  Readln(selections);
  Write('Out of how many elements? ');
  Readln(elements);
  answer := elements;
  for i := 1 to selections - 1 do
  begin
    elements := elements - 1;
    answer := answer * elements
  end;
  Writeln('Nonunique combinations = ', answer:0:0);
  answer := answer / Factorial(selections);
  Writeln('Unique combinations = ', answer:0:0)
end.






<a name="01a8_0012">
<a name="01a8_0013">
[LISTING FOUR]
<a name="01a8_0013">

{ telname.pas -- Display number for telephone "name" by Tom Swan }

program TelName;

var
  i: Integer;
  TelNumber: String;
  TelDial: array[0 .. 9] of String[3];
  LetterSet: set of Char;

{ Return telephone digit that corresponds to a letter C. }
function DigitToLetter(C: Char): Char;
var
  i, j: Integer;
begin
  C := Upcase(C);
  for i := 0 to 9 do
    for j := 1 to 3 do
      if (C = TelDial[i][j]) then
      begin
        DigitToLetter := Chr(i + ord('0'));
        Exit
      end;
  DigitToLetter := C  { Default }
end;

begin
  TelDial[0] := '   ';  TelDial[1] := '   ';
  TelDial[2] := 'ABC';  TelDial[3] := 'DEF';
  TelDial[4] := 'GHI';  TelDial[5] := 'JKL';
  TelDial[6] := 'MNO';  TelDial[7] := 'PRS';
  TelDial[8] := 'TUV';  TelDial[9] := 'WXY';
  LetterSet := ['A' .. 'P', 'R' .. 'Y'];
  Write('Enter telephone name: ');
  Readln(TelNumber);
  for i := 1 to length(TelNumber) do
    Write(DigitToLetter(TelNumber[i]));
  Writeln
end.




<a name="01a8_0014">
<a name="01a8_0015">
[LISTING FIVE]
<a name="01a8_0015">

{ telnum.pas -- Algorithm #6: Telephonic Mnemonic by Tom Swan }

program TelNum;

var
  TelNumber: String;
  TelDial: array[0 .. 9] of String[3];
  inString: String;
  outString: String;

function ValueOfChar(c: Char): Integer;
begin
  ValueOfChar := Ord(c) - Ord('0')
end;

procedure Permute(n: Integer);
var
  i, digit: Integer;
begin
  digit := ValueOfChar(inString[n]);
  for i := 1 to 3 do
  begin
    outString[n] := TelDial[digit][i];
    if (n = Length(inString)) then
      Writeln(outString)
    else
      Permute(n + 1)
  end
end;

begin
  TelDial[0] := '   ';  TelDial[1] := '   ';
  TelDial[2] := 'ABC';  TelDial[3] := 'DEF';
  TelDial[4] := 'GHI';  TelDial[5] := 'JKL';
  TelDial[6] := 'MNO';  TelDial[7] := 'PRS';
  TelDial[8] := 'TUV';  TelDial[9] := 'WXY';
  Write('Telephone number? ');
  Readln(inString);
  if (Length(inString) > 0) then
  begin
    outString := inString;
    Permute(1)
  end
end.


</PRE>
<P>

<P>

Copyright © 1993, Dr. Dobb's Journal


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.