CODEWITHSUNDEEP
algorithmlanguage-agnostic
MaiaVictor
MaiaVictor

Reputation: 53017

How to elegantly and imperatively generate the nth string of an alphabet?

Given an alphabet such as: ["a","b","c","d"], the sequence of all strings made up from characters of that alphabet is:

""
"a"
"b"
"c"
"d"
"aa"
"ab"
"ac"
...

Haskell can generate the nth element of that sequence elegantly and recursively:

nth :: Int -> String
nth n = reverse $ alphabet !! n where
    alphabet = [""] ++ concatMap (\ str -> map (: str) "abcd") alphabet

But that's inefficient. Using base conversions, you could try generating it imperatively as (using JavaScript just for demonstration):

function nth(n) {
  var str = "";
  while (n > 0) {
    str += String.fromCharCode(97 + n % 4);
    n = Math.floor(n / 4);
  }
  return str;
};

for (var i = 0; i < 64; ++i) {
  console.log(nth(i));
}

But that actually generates the following sequence:

""
"b"
"c"
"d"
"ab"
"bb"
"cb"
"db"
"ac"
"bc"
"cc"
"dc"
"ad"
"bd"
"cd"
"dd"
"aab"

Which is not what was desired: notice the missing "a", "aa", "ba", etc. I'm probably missing some simple operation to fixes the imperative implementation, thus, my question is: is there any elegant way to imperatively generate the nth string of an alphabet?

Upvotes: 2

Views: 197

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Insert n-- at the beginning of the while loop. If you want the results in short lexicographic order, reverse the string before printing.

Upvotes: 2

Related Questions