Restricted Index Display Sequence
I am puzzled on how to map a set of sequences to integers.
All sequences follow this rule:
A_0 = 1
A_n >= 1
A_n <= max(A_0 .. A_n-1) + 1
I'm looking for a solution that can, given such a sequence, compute an integer to perform a table lookup, and by specifying the index into the table, generate the sequence.
Example: For length 3, there are 5 valid sequences. A quick function to execute the next map (preferably in both directions) would be a good solution
1,1,1 0 1,1,2 1 1,2,1 2 1,2,2 3 1,2,3 4
- The goal of the exercise is to get a packed table with a 1-1 mapping between valid sequences and cells.
- Set size in a limited number of possible unique sequences.
- Now I don't know what the length of the sequence will be, but it will be a small constant known in advance.
- I'll get to that sooner or later, but though I would pick it to make the community “have fun” with the meantime.
these are different valid sequences
1,1,2,3,2,1,4 1,1,2,3,1,2,4 1,2,3,4,5,6,7 1,1,1,1,2,3,2
is not
1,2,2,4 2, 1,1,2,3,5
Related to this
source to share
There is a natural indexing sequence, but it is not easy to calculate.
Let's look at A_n for n> 0, since A_0 = 1.
Indexing is done in 2 steps.
Part 1:
Group sequences in places, where A_n = max (A_0 .. A_n-1) + 1. Name these steps of places.
- The steps are sequential numbers (2,3,4,5, ...).
- In non-step locations, we can place numbers from 1 to the number of steps with index less than k.
Each group can be represented as a binary string, where 1 is a step and 0 is not a step. For example. 001001010 means a group with 112aa3b4c, a <= 2, b <3, c <= 4. Since groups are indexed with a binary number, there is a natural indexing of groups. 0 to 2 ^ length - 1. Allows you to call the group binary order value of the groups.
Part 2:
Index sequences within a group. Since the groups define the step positions, only the numbers in the non-step positions are variable, and they are variable within certain ranges. Moreover, it is easy to index the sequence of a given group within this group with the lexicographic order of variable places.
It is easy to calculate the number of sequences in one group. This is a number like 1 ^ i_1 * 2 ^ i_2 * 3 ^ i_3 * ....
Combination:
This gives a 2-part key: <Steps, Group>
then it needs to be matched to integers. To do this, we have to find how many sequences are in groups that have an order less than a certain value. To do this, we first determine how many sequences are in groups of a given length. This can be calculated by going through all the groups and adding the number of sequences or similar with repetition. Let T (l, n) be the number of sequences of length l (A_0 is omitted), where the maximum value of the first element can be n + 1. What holds:
T(l,n) = n*T(l-1,n) + T(l-1,n+1) T(1,n) = n
Because there l + n <= sequence length + 1
are values ~ sequence_length^2/2
T (l, n) that can be easily calculated.
Next, you should calculate the number of sequences in groups of order less than or equal to a given value. This can be done by summing the values of T (l, n). For example. the number of sequences in groups with order <= 1001010 binary, is
T(7,1) + # for 1000000
2^2 * T(4,2) + # for 001000
2^2 * 3 * T(2,3) # for 010
Optimization:
This will give a mapping, but a straight forward implementation to combine key parts >O(1)
at best. On the other hand, the part of the Steps
key is small and by calculating the range Groups
for each value Steps
, the lookup table can reduce this to O(1)
.
I'm not 100% sure about the top formula, but it should be something like this.
With these notes and repetition, a sequence of sequences -> index and index -> can be made. But not so trivial :-)
source to share
This is a python function that can do the job for you, assuming you got these values stored in a file and passing the strings to the function
def valid_lines(lines):
for line in lines:
line = line.split(",")
if line[0] == 1 and line[-1] and line[-1] <= max(line)+1:
yield line
lines = (line for line in open('/tmp/numbers.txt'))
for valid_line in valid_lines(lines):
print valid_line
source to share