How to predict the length and offset of the sequence in and array?

Question

I have an input string similar to ABCDEFGHIJK from which a series of sequences has been generated into an array as following:

00: 'ABCD'
01: 'BCDE'
02: 'CDEF'
03: 'DEFG'
04: 'EFGH'
05: 'FGHI'
06: 'GHIJ'
07: 'HIJK'
08: 'ABC'
09: 'BCD'
10: 'CDE'
11: 'DEF'
12: 'EFG'
13: 'FGH'
14: 'GHI'
15: 'HIJ'
16: 'IJK'
17: 'AB'
18: 'BC'
19: 'CD'
20: 'DE'
21: 'EF'
22: 'FG'
23: 'GH'
24: 'HI'
25: 'IJ'
26: 'JK'
27: 'A'
28: 'B'
29: 'C'
30: 'D'
31: 'E'
32: 'F'
33: 'G'
34: 'H'
35: 'I'
36: 'J'
37: 'K'

The sequences in the array above has been generated by following these steps:

1. Set length to 4
2. Set offset to 0
3. Pick a sequence of length long characters from "ABCDEFGHIJK" (Input string)
4. Put the sequence at the bottom of output array
5. Increase offset by 1
6. If offset + length <= 11 (Input string's length) then goto 3
7. Decrease length by 1
8. If length >= 1 then goto 2
9. Exit

By looking at the output array, sequences in the array have a length which starts at 4 and gradually goes down to 1, and also an offset which is where in the input string the sequence has begun.

What I'm trying to achieve is to "predict" both the length and the offset of a sequence at a given index in the output array, only having the input string's length and index in the output array.

I'm preferably looking for a formula, however an algorithm which doesn't involve simulating the output array will work as well.

Answer 1

Let $n$ be the length of the string, and $k$ be the maximum length of the substring. Thus the first $n-k+1$ positions correspond to length $k$, the next $n-k+2$ to length $k-1$, and so on. Denote by $i_\ell$ the index at which substrings of length $k-\ell$ begin. We have $$ i_\ell = \sum_{t=k-\ell+1}^k (n-t+1) = \frac{[(n-k+1)+(n-k+\ell)]\ell}{2} = \frac{\ell^2}{2} + \ell\left(n-k+\frac{1}{2}\right). $$ Given $i_\ell$, we can solve for $\ell$: $$ \ell = \sqrt{(n-k+1/2)^2+2i_\ell}-(n-k+1/2). $$ Monotonicity shows that for arbitrary $i$, the floor of this expression still gives the correct value of $\ell$. This suggests the following algorithm:

1. Let $i$ be the input index.
2. Calculate $\ell = \lfloor \sqrt{(n-k+1/2)^2+2i}-(n-k+1/2) \rfloor$.
3. Calculate $i_\ell = \ell^2/2 + \ell(n-k+1/2)$.
4. Output length=$k-\ell$ and offset=$i-i_\ell$.

For example, let's take $i = 10$ in your case (where $n = 11$ and $k = 4$). Then $\ell = \lfloor \sqrt{7.5^2+20}-7.5 \rfloor = \lfloor 1.23\ldots \rfloor = 1$ and $i_\ell = 1^2/2 + 1\cdot 7.5 = 8$. Hence the length is $4-1=3$ and the offset is $10-8=2$.

Answer 2

Variables

In this answer I will use the following names for the variables:

• The n variable refers to the initial value of length (in the case above this is 4)
• The isl (input string length) variable refers to the length of the input string (11 in the case above)
• The index variable refers to the index of the output array.

Approach

To solve the problem and find a solution, we should first look at the details we got.

Input

The formula or algorithm we are looking for receives the following inputs:

• The index of the output_array
• The isl (length of the input string)

But this is not the only input. It also knows the initial value of length (in your example above it's 4). As mentioned above, we will call this value n.

Facts

From the algorithm you described in your question, we can derive the following facts:

Partitions of the output array

The output_array will have n partitions corresponding to the n different lengths (in your example above the lengths from 4 to 1). Each partition i has a length of $$\text{isl}-(n-i)+1$$ where i (the partition number) starts at 0. We notice, that the first partition is the smallest one and the last partition (where the sequences have a length of 1) is the largest one with a length of isl. From the formula we also see, that the length of the partitions increases from the first partition to last partition by 1.

Note: We count partitions starting at 0.

Deducting the Formula

We need two formulas. One for the length of the sequence at index and one for the offset of that same sequence in the input string.

The formula for length

The formula for the length must look something like this: $$\text{length} = \overbrace{\text{n}}^{\text{minuend}} - \overbrace{\text{something depending on index}}^{\text{subtrahend}}$$

For the first partition (partition 0) the subtrahend shall be 0. For the second (partition 1) it shall be 1 and so on.

Indicator function

As we can see, we need a function, which can tell us, in which partition the index is in. A thing with such a property is like an indicator function. It could look like:

$$\text{partition_number}(\text{index}) = \begin{cases}0,&\text{if index in partition 0}\\1,&\text{if index in partition 1}\\\ldots\end{cases}$$

An easy way to find such a function is to have an indicator function, which can tell us, if index is in a partition a, where a is at least i. Something like:

$$f(\text{index},i) = \begin{cases}1,&\text{if index in partition a > i}\\0,&\text{else}\end{cases}$$

Because then we would just have to sum the result of f for all partitions and would directly have our subtrahend.

To define such a function f, we need to know at least the left boundary of partition i. We can obtain the left bound of partition i by:

$$\text{left_bound}(i) = i*\overbrace{(\text{isl}-n+1)}^{\text{Size of first partition}}+\overbrace{\frac{1}{2}*(i-1)*i}^{\text{Correction number for partition growth}}$$

So our indicator function looks like:

$$f(\text{index},i) = \begin{cases}1,&\text{if } \text{left_bound}(i)<=\text{index}\\0,&\text{else}\end{cases}$$

With this function we can now define our partition_number function as following:

$$\text{partition_number}(\text{index})=\sum_{i=0}^{n-1}{f(\text{index},i)}-1$$

With the partition_number for our subtrahend we can now define our formula for the length_at_index:

$$\text{length_at_index}=n-\text{partition_number}(\text{index})=n-\sum_{i=0}^{n-1}{f(\text{index},i)}+1$$

The formula for offset

We can directly make use of the partition_number and left_bound function we defined above:

$$\text{offset_at_index} = \text{index}-\text{left_bound}(\text{partition_number}(\text{index}))$$

A Solution in Javascript

And here the solution of above written in Javascript:

function getLeftBoundOfPartitionI(i, isl, n) {
    return i * (isl - n + 1) + .5 * (i - 1) * i
}

function isIndexInPartitionI(index, i, isl, n) {
  return index >= getLeftBoundOfPartitionI(i, isl, n) ? 1 : 0
}

function getPartitionNumber(index, isl, n) {
    partition = 0
    for(var i = 0; i < n; i++) {
    partition += isIndexInPartitionI(index, i, isl, n)
  }
  return partition - 1
}

function lengthAtIndex(index, isl, n) {
    return n - getPartitionNumber(index, isl, n)
}

function offsetAtIndex(index, isl, n) {
  partitionNumber = getPartitionNumber(index, isl, n)
    return index - getLeftBoundOfPartitionI(partitionNumber, isl, n)
}

document.body.innerHTML = offsetAtIndex(16, 11, 4)  // yields 8