Dr. Breuer:

I can in 100 digits arrange to have each of the values in the range [0..100) appear in that list of 100 digits, each being thus represented exactly one time.  Thus:

0102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990

Notice that the two-symbol representation of the value zero is formed from the first and last symbols of the list; i.e., 00; it is hard to represent a bracelet using a text editor.

So, can a similar list (string, symbol sequence, ...) be constructed such that it represents within its extent all of the values [0..102), where the symbol sequences are all three digits long; 0 is 000, 1 is 001, ... 99 is 099...101 is 101, while at the same time, the overall length of the sequence is just 101 symbols?

For integral powers of the radix of the notation scheme (10 in the case of decimal numbers), I can easily construct a sequence that represents all values [0..10^n), with each representation being a sequences of n symbols.

We see in the above list of 100 digits that every value in the interval [0..100) is represented by a sequence of two digits; i.e., 00 to 99.

Please see my dataset

https://www.researchgate.net/publication/260230314_Characters_and_Derivation_of_the_Maximally_Disordered_Genome?ev=prf_pub

for details on the procedure for constructing such integral power sequences.

Data Characters and Derivation of the Maximally Disordered Genome

Notice that I might also construct a sequence as follows,

00 01 10 02 20 03 30 04 40 05 50 06 60 ...

Removing the spaces, we have

00011002200330044005500660...

And we see that not only are the values 00 .. 99 represented, but so to is the value 000; or, the representation 00 occurs not once but many times.  But, this sequence is not of length equal to an integral power of the radix of the symbol set (i.e., 10 for decimal representation). Indeed, the length is two times the square of the cardinality of the symbol set.

One approach would be to take all your numbers, 0,..,n, regard each as a string of k digits, and create a graph: the edges are labeled with the numbers 0, ..., n, and two edges meet at a vertex if the first k-1 symbols of 1 are the same as the last k-1 symbols of the other (that is if they could appear consecutively in the list of windows of size k reading down your sequence).

Then finding a sequence with the properties that you wish would be the same as finding an Euler circuit in the graph --- this is possible if  and only if the degrees of the graph are all even and the graph is connected.  This should be easy to check for any given n.

Interesting, a graph method of showing that permutations have the property of being overlaid, such that a permutation of n is represented in n digits.  Thus,

0102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990

can be shown to fit such a graph.  I can generate such permutations very quickly.  Further, the shustrings for all loci of the above string are of length 2.  So, this sequence is maximally disordered.

Dr. Breuer:

You make an error in the algorithm that I specify.

[391] -> [091]  this is wrong.

The case would be [391] -> [91x] where x is an element of {0...9}.

Indeed, yes, the graph is connected.  The more obvious approach to making a directed graph --- labeling the vertices with the strings, and putting in an edge if the strings overlap --- isn't as useful since it leads to the problem of finding a hamilton cycle in the graph, a problem which (in this case can be solved but) is in general not known to be easily solvable.  

The algorithm is assisted if you think of the sequences 00, 01, 02, ..., 98, 99 as being "tiles" that we overlay.  So, the left n-1 symbols of a tile we may call the "left key"  and similarly, the right n-1 symbols of a tile, we may call the "right key."

The algorithm for maximally disordered sequence construction is that the tiles of the sequence are ordered such that the right-key of the previous tile is equal to the left-key of the next tile.

It may be of interest that the algorithm that I use is able to compute these overlay-able permutations, these Hamiltonian cycles on a graph, rather quickly.  Indeed, for one hundred million digits, a sequence is computed in under 13 seconds on a single core of a 3.4GHz Intel i7 processor.

So, one of the lessons is that maximal disorder correlates with an Hamiltonian path.

Can you relate your graph to the assembly sequence I give earlier in this discussion.  I do not understand your graph.  Please be patient with me.

The problem I have with your graph is that it is made of tiles of differing length; some tiles are two symbols long and some tiles are three symbols long.  This can be used to describe sequences of length between integral powers of the radix.  Is this what your graph is intended to show?

Probably, there may be something based on de bruijn sequences,graphs or torus...but i'm not sure.

That will be a great compressor if it works on real genomic sequences (a bit far from random strings).

First, there must come to a complete understanding of the mechanics of these sequences.

To try to help clarify what I said, and what Peter has commented on: I propose the following: we are asking for all words of length k to be represented as consecutive sub-words exactly once: 

We create a directed graph: the edges correspond to the words of length k (padded with 0's at the front if need be).  And in-edge and and out-edge meet at a vertex if the k-1 suffix of one is the k-1 prefix of the other.  An *Euler* circuit in this graph corresponds to what you are looking for, William.

Euler circuits are easy to find --- which is why this formulation is better than making the nodes have labels corresponding to words of length k, and edges corresponding to words of length k-1.   

As Vincenzo has said, this is a case of looking for de Bruijn sequences --- but not of dB seqs going through all words up to 10^k, rather up to some smaller n.

Are you sure that this is the application you are interested in?  It's possible that there is a broader context in which you wish to ask your questions, and you've specialized them to asking about [0,...n], rather than asking the more interesting question.

For example, given a collection of subwords of length k, is there a word of an appropriate length that contains them (and only them) each exactly once?

Regarding what Peter said above, about inputs and outputs (specifically about there being 2 inputs and 10 outputs --- that is exactly the digraph generalization of the graph theoretic result about Euler circuits. For such a circuit to exist, there must be as many inputs as outputs at every node.

The point of all this work is to understand the nature of shustrings, the conditions under which shustrings are minimised in length, and the correlation between shustring length distributions and sequence disorder.  Again, for the gene jockey, it is very important to minimise primer length, as this optimises the cost of primers while simultaneously maximising the specificity of primers; this has the benefit of concentrating the work of the gene jockey on the DNA region of interest.

Related to this work is that the sequences that are identified by my algorithm (these have lengths equal to integral multiples of the radix of the symbol set) are maximally disordered.  Indeed, one of my goals is to find another worker who can show me how one of these sequences (that my algorithm generates) can in fact be modified so as to represent greater disorder.  I believe it cannot be done, and have what I think is strong evidence to support the claim.

Further, I have discovered how these sequences may be inter-converted, without more than one search; there is a means to shuffle the tiles of such a sequence in a way that ensures that all the shustrings remain unchanged in length, even as their locus does change.

There is a proper sub-set of the permutations, each element having exactly the same degree of disorder, and all are inter-convertible.

The inputs versus outputs makes sense.

What I want to find is that there exists at least one path, such that the shustrings of a successive set of ever longer symbol sequences grow in a regular way, where the difference in length between any two shustrings is never more than one.

Does the bracelet grow in a way that shustrings appear in *nice* order?

I know this is a vague question but it is the best I can do.  Can you point me to suitable books and papers such that I can climb the learning curve, a bit?

An interesting twist is that the equation

(s!) ^ (s ^ (n-1)), where s is the radix and n is the length of tiles

does not seem to apply to sequences built of just two symbols; i.e., for binary numbers.

The equation does apply to all symbol sets having a cardinality strictly greater than 2.

From a dataset posted on my RG profile, comes this quote:

"The only reasonable definition for randomness over a symbol sequence drawn from a finite symbol set (such as the integers that are constructed from sequences of decimal digits) is based upon mutual contextual difference between elements of the sequence. That is, two instances of one symbol within the sequence are differentiable in terms of the other symbols that surround the two; each instance has a different sub-sequence just ahead of it, and the degree of differentiability between the two instances is inversely related to the length of these surrounding sub-sequences; it happens that these surrounding sub-sequences can be minimised through a clever use of permutation, and the fact of such minimisation can be verified by the use of shustring analysis."

My ultimate concern is disorder, its nature and maintenance, particularly as applied to symbol sequences.

It appears that only with well selected additions of new symbols to a sequence will the disorder of the sequence be maintained.  Further, it might be that restrictions like "the lengths of all pairings of shustrings differ by at most one" can be maintained only by the addition of pairs of digits.

For the sequence  (recall, it is a bracelet)

0123456789

all shustrings are of length one.  That is, every locus is uniquely identified by a single symbol.

Let us append to the end the digit 0.

01234567890

The shustrings are now in the distribution of 2 having a length of two, and 9 having a length of one.   The two long shustrings are 00 and 01.

Let us now append to the end the digit 9.

012345678909

So, now we have 8 shustrings of length eight (1 2 3 4 5 6 7 8), 2 shustrings of length two (09 and 01) and 2 shustrings of length three (909 and 901) for a total of 12 shustrings.

I would like to find a construction mechanism that allows shustrings to increase in length in a uniform fashion, such that the difference in length between any two shustrings is never greater than one.

I would also like to find any existing work that even remotely touches upon this analysis mechanism.

Frankly, given the importance of analysing symbol sequences (like for code-breaking, genomics, number theory), I am quite surprised that I can find no prior work on this topic.

Your question reminds me of De Bruijn Sequences.

I came at this problem from the point of view of genetics, noticed a regularity associated with disorder, and developed an algorithm that exploits this regularity so as to either generate maximally disordered sequences on a symbol set, or to find shustrings, given a sequence and symbol set.

With much discussion and instruction coming from a variety of respondents, I have now come to understand that my software finds Eulerian paths on de Bruijn graphs, that tile keys correspond to the vertices of a de Bruijn graphs, and that shustrings are related to de Bruijn graph vertices (vertices are one short of a shustring).

I thank you all very much for your comments and suggestions.

Using Dr. Breuer's notation, my notion of tile corresponds to a node.  I see edges as not needing a label; it is clear that [xyz] -> [yzw] involves the appending of 'w' to the growing sequence; also, the suffix-key of [xyz] corresponds to the prefix-key of [xyz] (i.e., [xy]).  All that is important is that only one edge covers the path from [xyz] -> [yzw].  A graph of nodes, each described by a three symbol sequence, would correspond to a symbol sequence composed of 3-tiles in my notation; very clearly my work has been to develop an alternative (perhaps novel) approach to the generation and analysis of De Bruijn sequences.

I obtained the name 'bracelet' from this Wikipedia article:

http://en.wikipedia.org/wiki/Necklace_%28combinatorics%29

For a bracelet, all beads are distinct, just as all tiles are distinct.  Some parts of the Wikipedia article are confusing, if not self-contradictory.

As to the issue of maximal disorder, I claim that the only reasonable definition  for randomness over a symbol sequence drawn from a finite symbol set is the mutual contextual difference between elements of the sequence.  Does a reader have a better idea for a discriminating metric?

Regarding the equation derived in my dataset, Characters and Derivation of the Maximally Disordered Genome, that is reproduced in the Wikipedia article on De Bruijn sequences:

http://en.wikipedia.org/wiki/De_Bruijn_sequence

with one exception - the denominator is an exponential in the Wikipedia article, and the denominator of the equation I derived is not an exponential.  This is curious to me, and I am hoping a reader can show me the error that I make in deriving the equation.

OK,

1. My algorithm finds de Bruijn sequences without explicitly constructing a de Bruijn graph.

2. De Bruijn sequences correspond to a subset of the permutations.

3. De Bruijn sequences are maximally disordered.

Any complaints?

I rather think that shustring histograms are a solid means of measuring sequence disorder.  See this post for more information on such use of shustrings:

https://www.researchgate.net/post/Abstract_Naive_Genomics?_tpcectx=profile_questions

Not all sequences are maximally disordered.  In such case the shustrings differ in length, such as are the shustrings of the one million random digits produced by the RAND Corporation.  For a maximally disordered sequence of symbols, the shustrings all have the same length.  That is a measure both qualitative and quantitative.  I suggest you read Haubold's paper on sequence comparison without alignment.

Your measure is not well understood by me, though informational entropy is related to maximal disorder.  If I put a sequence to the test, producing one with my software and then using the software of other practitioners, as a means to compute the entropy of the sequence, the computation is always of a maximal value; i.e., 3.32 units of entropy per digit in the sequence.  I have given examples in previous posted questions.

Also, are you familiar with the work of Gatlin?

If you move digits without care, you will obtain longer shustrings. If you are instead careful, then the movement of digits obtains no degradation of shustring length distribution.

Now, the arrangement of shustrings in maximally disordered sequences is constrained; this is why you cannot without care move digits around.  I term such rearrangements (careful ones) as shuffles. 

In De Bruin terminology (graph theory terminology?) this is known as a different Eulerian/Hamiltonian path (they are apparently equivalent).

Found the right paper!  See:

http://www.ams.org/journals/bull/1934-40-12/S0002-9904-1934-05988-3/home.html

A Problem in Arrangements, MH Martin, 1934.

The first page of Martin's paper provides an exact description of my view.

de Bruijn gives some clarity to the possibilities in this paper

http://alexandria.tue.nl/repository/books/252901.pdf

There is also the work of Pevzner.  See for instance:

http://www.pnas.org/content/98/17/9748

Figure 5 of this paper on The Origins of Combinatorics on Words shows that for de Bruijn graphs, the nodes correspond to the keys of my tile construction method, and the edges of de Bruijn graphs correspond to the extensions of my tile construction method.  Clearly, being able to find an Eulerian path is equivalent to constructing the graph.

http://www.sciencedirect.com/science/article/pii/S0195669805001629

Is it said in any paper related to de Bruijn graphs that one may find every Eulerian path by rotating the edge assignments exiting any node?

Counting the number of Euler tours (and hence generating them in some nice way) is a hard problem.  Even for graphs where every vertex has degree 4, the problem is #P hard.  I suspect that for digraphs, the situation is similar.

Take this 2-tile, maximally disordered digit sequence:

0102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990

We understand that this sequence is obtained from an Eulerian path over a de Bruijn graph.  We may choose any key from a 2-tile, and shuffle the extensions, and in so doing, generate a different maximally disordered sequence.  The proof is that the lengths of shustrings remains a constant (2) even as the locations of particular sub-strings change.  For instance, we find all the keys of value 1; to indicate their location, I've inserted the "-" character after the key in the given sequence

01-02030405060708091-1-21-31-41-51-61-71-81-922324252627282933435363738394454647484955657585966768697787988990

-02030405060708091-1-21-31-41-51-61-71-81-92232425262728293343536373839445464748495565758596676869778798899001

We now shuffle these segments, taking every other segment, first odd, then even:

-1-31-51-71-92232425262728293343536373839445464748495565758596676869778798899001-02030405060708091-21-41-61-81

Removing the hyphens, we have:

1315171922324252627282933435363738394454647484955657585966768697787988990010203040506070809121416181

Computation of shustring lengths for both sequences yields histograms with but one peak ---> 2.

If keys were of length two, then the pair of characters to the left of any inserted hyphen will be the same, and for sequences on the digits, there will only be ten inserted hyphens per shuffle.

It is very easy to keep track of the locations of keys, and so the time to compute a new Euler path from a known Euler path is O(1).

Just an outside remark because i am not familiar with the topic and terminology: Apparently, your reasonings are based on fixed-base number systems. I have been working on some interesting features of the factorial number system that increases the base at every consecutive step. I found some very nice (at least for me!) properties of periodicity in this system. Can you transform your problems into this system? Maybe in some cases you get easier or more graceful expressions in this way.

István, might you perhaps list a few relevant papers, or give some examples?

William, the factorial system has a lot of well-known features, yet it has relatively few references as compared with other number systems. Some of its characteristics are close to those of continued fractions which are much more popular in literature.

The greatest disadvantage of the factorial system is that it needs infinitely many symbols, one for each natural number, respectively. At the n-th place after the radix point the maximal digit is n, and the place value is 1/n+1)!. It follows that all the rationals can be expressed in finite form, p/q terminating not later than at 1/q!. (Beautiful consequences for the extension of reciprocals of primes and prime powers!)

This means that new types of periodic expressions are released for irrational numbers. For example, e = 2.111...

I found a simple method to create new periodic irrationals from a periodic irrational. For example, e/6 = 0. 022421 276942 4(12)(10)(14)63... Here the group 022421 can be called  "the base period"; and 254521"the step period". Each consecutive hextet can be computed from the previous one by adding the digits of the step period to the digits of the previous hextet.

Piles of intriguing challenges can be raised from this start. For what operations is the set of periodic numbers closed in the set of real numbers? (I proved that the set of periodics is still countably infinite.) Neither pi, nor even e2 seems to be periodic. What set of real numbers can be handled by linear combinations of, not rational numbers, but the extended set of periodic numbers? How can infinite sums of periodics be created to converge to a limit? For example, 0.12345...+0.01234...+0.00123...+0.00012... ... = 1.02030405...  = e/2.

Still another question: Research results are known about the distribution of digits in the expression of, say, pi or e, in the decimal system. What about the distribution of digits of a non-periodic irrational in the factorial system? How can the question itself be properly formulated for this problem?

It appears that alteration of the Eulerian path requires two items if information.  The first is the location of keys within the sequence.  The second is the ordering of those keys and in particular, the identities of the left-most key and the right-most key.  All of the segments between these two keys may be freely reordered (in C, think re-linked nodes in a linked-list); one must ensure that no link is made between tiles bearing the left-most and right-most keys.  With these restrictions, one can produce a good many Eulerian paths, given knowledge of just one such Eulerian path, and the time to computation of a new path from a known path is O(1).  Moreover, one suspects that this method (shuffling of edge assignments) provides sufficient means to cover all possible Eulerian paths for any given de Bruijn graph.

Note, one need not search for the left-most and right-most keys; this data is available at just the right time (so as to be noted) during the construction of the de Bruijn graph, and is constant for any given de Bruijn graph.

William, 

That is indeed correct in terms of constructing lots of paths.  My points about systematically constructing all of them, or counting them, being difficult, stands.

If I can construct lots of paths, then there is only a need to order their construction, so that all possible paths are visited.  To do that, we need to keep track of the current permutation of the edge assignments, for each node of the de Bruijn graph.  The solution looks to be O(n^2).

I'm not sure how it will apply to your particular instance of the problem, but in general for a graph with fixed in and out degrees at each vertex, I think that there are likely to be way more than polynomially many euler tours.  

At each node, the number of permutations of the n edges is (n-1)!, and so the number of tours is (n-1)! raised to a power equal to the number of nodes.  Why would this not be correct?

Would this construction however yield O(n ^ number_of_nodes)?

In any case, the paths can be generated in orderly fashion:

0. select some Eulerian path; a tour, if you like;

1. list the nodes in some order

2. repeat:

a. for the lowest order node, generate all permutations of the symbols, and for each permutation print the tour.  NB - these permutations are also ordered.  So,

b. for all higher order nodes W, when the immediately lower order node is found to have generated all permutations, generate the next permutation for W, and if W does not return to the initial permutation of edge symbol assignment, then return to the lowest order node, where it is set to again generate all permutations of its edge assignments.

This of course stops when the left-most node has generated all of its permutations, and finds itself ready to repeat its cycle.

It may take a long time but, all paths are covered by this algorithm.

Further, because we may label permutations, it follows that we may also label in distinctive fashion every Eulerian tour; each tour is known by the toured de Bruijn graph and the particular permutation of the edge symbol assignments that are applied to the de Bruijn tour.

William, 

You do indeed get upper bounds for the number of tours in this sort of fashion, but they may not be particularly *good* bounds.  And yes, if you try to generate random tours with something approaching uniform probability, it may take a long time!

However poorly may bounds be by my method obtained, it is nevertheless true that my method generates all de Bruijn sequences.  That is, for any given de Bruijn graph, my method finds all corresponding de Bruijn sequences.