A New Kind of Science: The NKS Forum > Pure NKS > Enumerating strings
Author
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 113

Enumerating strings

Here is a function that people might find useful when performing enumerations. It enumerates all strings with k colors, of any length.

enum[n_,k_]:=With[{tmp=Length[IntegerDigits[(k-1) n+1,k]]-1},
IntegerDigits[n-(k^tmp -1)/(k-1),k,tmp]]

It does not have any gaps, and here is its inverse function:

unenum[ls_,k_]:=(k^Length[ls] - 1)/(k-1)+FromDigits[ls,k]

It relies on the formula for geometric sums, and the efficiency of the IntegerDigits function.

For comparison, some other enumeration functions compute

the strings of k colors of fixed length with IntegerDigits[n,k,len]

finite strings of arbitrary length and arbitrary colors with the Leibniz-Godel function (p.1120)

strings of fixed length with arbitrary colors with the pairing function
(p.1127 and the recent forum thread).

Report this post to a moderator | IP: Logged

11-10-2005 05:46 PM
Val Smith

Registered: Jun 2005
Posts: 39

Just for clarification:

Is this a general function for any Base
to calculate which digit of a Champernowne's Constant is the first one that contains a specific Integer?

If so, the inverse function would simply "count" if used properly in counting order.
If not, what kind of number sequences does the inverse function generate when strings are denumerated in counting order?

__________________
If something is zero, and zero is nothing, then something must be nothing.

Report this post to a moderator | IP: Logged

11-11-2005 08:48 PM
Jesse Nochella
WRI

Registered: Mar 2004
Posts: 132

Great function. This can be used in place of IntegerDigits[n, k] for enumerating inital conditions, so that sequences such as {0,0} and {0,0,0} can both be included in the sweep.

Report this post to a moderator | IP: Logged

12-12-2005 10:16 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us