Constrained Sequence to Index Mapping

Question

I'm puzzling over how to map a set of sequences to consecutive integers.

All the 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 will be able to, given such a sequence, compute a integer for doing a lookup into a table and given an index into the table, generate the sequence.

Example: for length 3, there are 5 the valid sequences. A fast function for doing the following map (preferably in both direction) 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 point of the exercise is to get a packed table with a 1-1 mapping between valid sequences and cells.
• The size of the set in bounded only by the number of unique sequences possible.
• I don't know now what the length of the sequence will be but it will be a small, <12, constant known in advance.
• I'll get to this sooner or later, but though I'd throw it out for the community to have "fun" with in 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

these are not

1,2,2,4
2,
1,1,2,3,5

---

Related to this

Answer 1

This is a python function which can do the job for you assuming you got these values stored in a file and you pass the lines 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

Answer 2

Given the sequence, I would sort it, then use the hash of the sorted sequence as the index of the table.

Answer 3

I think hash with out sorting should be the thing.

As A0 always start with 0, may be I think we can think of the sequence as an number with base 12 and use its base 10 as the key for look up. ( Still not sure about this).