Random contiguous slice of list in Python based on a single random integer

Question

Using a single random number and a list, how would you return a random slice of that list?

For example, given the list [0,1,2] there are seven possibilities of random contiguous slices:

1. [ ]
2. [ 0 ]
3. [ 0, 1 ]
4. [ 0, 1, 2 ]
5. [ 1 ]
6. [ 1, 2]
7. [ 2 ]

Rather than getting a random starting index and a random end index, there must be a way to generate a single random number and use that one value to figure out both starting index and end/length.

I need it that way, to ensure these 7 possibilities have equal probability.

Answer 1

Simply fix one order in which you would sort all possible slices, then work out a way to turn an index in that list of all slices back into the slice endpoints. For example, the order you used could be described by

• The empty slice is before all other slices
• Non-empty slices are ordered by their starting point
• Slices with the same starting point are ordered by their endpoint

So the index 0 should return the empty list. Indices 1 through n should return [0:1] through [0:n]. Indices n+1 through n+(n-1)=2n-1 would be [1:2] through [1:n]; 2n through n+(n-1)+(n-2)=3n-3 would be [2:3] through [2:n] and so on. You see a pattern here: the last index for a given starting point is of the form n+(n-1)+(n-2)+(n-3)+…+(n-k), where k is the starting index of the sequence. That's an arithmetic series, so that sum is (k+1)(2n-k)/2=(2n+(2n-1)k-k²)/2. If you set that term equal to a given index, and solve that for k, you get some formula involving square roots. You could then use the ceiling function to turn that into an integral value for k corresponding to the last index for that starting point. And once you know k, computing the end point is rather easy.

But the quadratic equation in the solution above makes things really ugly. So you might be better off using some other order. Right now I can't think of a way which would avoid such a quadratic term. The order Douglas used in his answer doesn't avoid square roots, but at least his square root is a bit simpler due to the fact that he sorts by end point first. The order in your question and my answer is called lexicographical order, his would be called reverse lexicographical and is often easier to handle since it doesn't depend on n. But since most people think about normal (forward) lexicographical order first, this answer might be more intuitive to many and might even be the required way for some applications.

Here is a bit of Python code which lists all sequence elements in order, and does the conversion from index i to endpoints [k:m] the way I described above:

from math import ceil, sqrt
n = 3
print("{:3} []".format(0))
for i in range(1, n*(n+1)//2 + 1):
    b = 1 - 2*n
    c = 2*(i - n) - 1
    # solve k^2 + b*k + c = 0
    k = int(ceil((- b - sqrt(b*b - 4*c))/2.))
    m = k + i - k*(2*n-k+1)//2
    print("{:3} [{}:{}]".format(i, k, m))

The - 1 term in c doesn't come from the mathematical formula I presented above. It's more like subtracting 0.5 from each value of i. This ensures that even if the result of sqrt is slightly too large, you won't end up with a k which is too large. So that term accounts for numeric imprecision and should make the whole thing pretty robust.

The term k*(2*n-k+1)//2 is the last index belonging to starting point k-1, so i minus that term is the length of the subsequence under consideration.

You can simplify things further. You can perform some computation outside the loop, which might be important if you have to choose random sequences repeatedly. You can divide b by a factor of 2 and then get rid of that factor in a number of other places. The result could look like this:

from math import ceil, sqrt
n = 3
b = n - 0.5
bbc = b*b + 2*n + 1
print("{:3} []".format(0))
for i in range(1, n*(n+1)//2 + 1):
    k = int(ceil(b - sqrt(bbc - 2*i)))
    m = k + i - k*(2*n-k+1)//2
    print("{:3} [{}:{}]".format(i, k, m))