Programming Corner from Icon Newsletter 18

April 23, 1985; Icon Version 5

There were several interesting solutions to the anagramming problem posed in the last Newsletter. The most efficient solution, at least when working on a large amount of data, follows:

procedure anagram(s)
   local c, s1

   s1 := ""               # start with the empty string
   every c := !cset(s) do # for every character in s
   every find(c,s) do     # and every time it occurs in s
   s1 ||:= c              # append one
   return s1
end

The heart of this solution is to use cset(s) to obtain an ordered set of the characters in s. It is interesting that it is noticeably more efficient to use find instead of upto in the solution. The difference does not lie primarily in the functions themselves. What else is at work here?

It is also faster to append the characters one at a time than to count the number of each and append them in groups, as in

procedure anagram(s)
   local c, i, s1

   s1 := ""                     # start with empty string
   every c := !cset(s) do {     # for each character in s
      i := 0 every(find(c,s)) do    # count the number
      i +:= 1 s1 ||:= repl(c,i) # append that many copies
      }
   return s1
end

Why should this be?

Randal Schwartz submitted a number of interesting solutions in addition to one similar to the first solution above. One of his solutions uses a table of characters and their counts:

procedure anagram(s)
   local c, t

   c := table(0)
   s ?:= {
      while c[move(1)] +:= 1 ""
      }
   every t := !sort(c,1)
      do s ||:= repl(t[1], t[2])
   return s
end

This solution is about twice as slow, when working on a large amount of data, as the first one above, probably because of time spent in table lookup and garbage collection (due to the larger amount of storage needed for tables).

An even more interesting, albeit admittedly inefficient, solution from Randal Schwartz is the following one that puts each character of s in a separate table element:

procedure anagram(s)
   local t

   t := table()
   s ?:= {
      while t[[]] := move(1)
      ""
      }
   every s ||:= (!sort(t,2))[2]
   return s
end

Do you see why there is a separate table element for each character?

Icon home page