9772

Universal String Enumeration

This Demonstration shows a universal enumeration of all strings, of any length and any number of symbols. The sample button shows a series of the strings, together with their indices and weights. The other buttons show details of the algorithm for the same sample, or allow selection of an index or string and then generate the corresponding string or index, respectively.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

It is not hard to create a list of strings of some particular length and number of characters used. A more complicated enumeration specifies not only the number of characters but allows all possible lengths [1]. Here a method is shown for listing all strings of all possible lengths and all possible characters (or symbols).
Snapshot 1: the "sample with details" button gives a series of indices with associated strings (beginning with the index selected by the slider), shown with details—the thumbnail shows the same view without the details
Snapshot 2: in "index -> string" mode, you select an index by using the slider, and the string generated by the function UnrankString is shown: index 43 gives the string "ABC"
Snapshot 3: in "string -> index" mode, you can select a letter of the alphabet and then a string from the dropdown list, and the RankString function returns the index of that string: here is the string "MATHEMATICA" and its index
The enumeration algorithm is based on integer compositions: there are ways of writing as the sum of positive integers (where order counts). Since the "weight" of a string is here simply the sum of the character weights (with A having weight 1, B weight 2, etc.), there are then strings of weight . The index is used both to select the weight of the string and to indicate which integer composition is intended. First we find , the largest power of 2 that is less than the index. This is the offset to be subtracted from the index to give the reduced index, which is then treated as a binary number whose bits signal the presence of a comma or a plus sign between the 1s in the "meaning"). Finally the string (which by construction will have weight ) is generated from the integer composition: 1 represents the first character, 2 the second, and so on. This method first produces all strings of weight 1, then all strings of weight 2, and so on. Short strings with characters near the beginning of the alphabet appear early in this enumeration.
Although the functions here are limited to the uppercase characters A–Z, assuming access to some universal character list (not necessarily finite, merely countable) all lists of all strings of all characters will appear in the string enumeration.
References:
[1] T. Rowland, "Enumerating Strings," The NKS Forum.
[2] "Composition (number theory)" on Wikipedia (last modified on 28 January 2010).
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+