wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Enumerating strings
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
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

Old Post 11-10-2005 05:46 PM
Todd Rowland is offline Click Here to See the Profile for Todd Rowland Click here to Send Todd Rowland a Private Message Click Here to Email Todd Rowland Edit/Delete Message Reply w/Quote
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

Old Post 11-11-2005 08:48 PM
Val Smith is offline Click Here to See the Profile for Val Smith Click here to Send Val Smith a Private Message Click Here to Email Val Smith Edit/Delete Message Reply w/Quote
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

Old Post 12-12-2005 10:16 PM
Jesse Nochella is offline Click Here to See the Profile for Jesse Nochella Click here to Send Jesse Nochella a Private Message Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

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

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives