Algorithm for splitting a line into intervals

Question

I am looking for an algorithm that splits an integer range [0 - n] into a fixed number of k intervals (not necessarily all of same length). So if n = 15 and k = 8 then I want to split 0 - 15 into 8 intervals, I could do: 0 2 4 6 8 10 12 14 15

If I want to split into 10 intervals I could do: 0 2 3 5 7 9 11 12 13 14 15

What could be an easy algorithm that generates an array [0 .. k] that specifies the jump at each step?

EDIT: 1 <= k <= n. what I want is to spit out an array [0 .. k] that goes from a[0] = 0 to a[k] = n. So the end points are fixed as 0 and n. It would also be good if the intervals are as close to the same length as possible.

Answer 1

If random length intervals are permissible:

1. Fill an array with the numbers 1 through n-1
2. Shuffle the array using, e.g., Fisher-Yates shuffle
3. Select the first k-1 entries and sort them
4. Prepend 0, append n

This results in k+1 random but ordered values between 0 and n, which define k intervals. Using a shuffle guarantees that the intermediate k-1 values are all unique. This would be O(n) for the shuffle, O(k log k) for the re-sort.

Here's a Ruby implementation:

def segment_line(n, k)
  raise "invalid args" if n < 1 or k < 1 or n < k
  a = Array.new(n-1).map.with_index {|x,i| i+1}
  if n > k
    a = a.shuffle[0...k-1].sort
  end
  a.unshift(0).push(n)
end

p segment_line(15, 8)      # => [0, 1, 2, 6, 10, 11, 12, 14, 15]
p segment_line(15, 15)     # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

You'll get different answers each time you run it (except when n == k), but they'll always be valid answers for your stated specification.

Answer 2

If you want as close as possible you can do the following.

q = (n+1)/k    //Integer division
r = (n+1)%k
for i = 0 to i=k
    a[i] = q*i + min(r,i)

I am using a slight convention change, and is that the intervals are formed like [a[i], a[i+1]), that is, closed one the left, and open on the right, so that is why a[k] = n+1, but because the interval is open, you will get the correct result.

Answer 3

With

s = starting value
n = ending value
k = num of values

where

s <= n to ensure a valid range

k > 1 it is necessary an starting and an ending points

n-s+1 >= k to ensure there are non repeating values

lets define x = 1 + ((n - s + 1)-k)/(k-1)

so for 0 <= i < k we have a[i]=round(s+i*x)

JS sample code. Tested from windows commandline as cscript //nologo steps.js

for (var s = 0 ; s < 10 ; s++ )
for (var n = s ; n < s + 15 ; n++ )
for (var k = 2 ; k <= ( n - s + 1 ) ; k++ ) printRanges( s, n, k );


function printRanges( start, end, steps ){

    var s=start;
    var n=end;
    var k=steps;

    WScript.StdOut.Write('s='+s+', n='+n+', k='+k+ ' : ');

    var x=1+((n-s+1)-k)/(k-1);

    for (var i=0; i < k; i++) {
        WScript.StdOut.Write( Math.round(s + i * x ) + ' ' );
    };
    WScript.StdOut.WriteLine('')
}

And the result

s=0, n=1, k=2 : 0 1 
s=0, n=2, k=2 : 0 2 
s=0, n=2, k=3 : 0 1 2 
s=0, n=3, k=2 : 0 3 
s=0, n=3, k=3 : 0 2 3 
s=0, n=3, k=4 : 0 1 2 3 
s=0, n=4, k=2 : 0 4 
s=0, n=4, k=3 : 0 2 4 
s=0, n=4, k=4 : 0 1 3 4 
s=0, n=4, k=5 : 0 1 2 3 4 
s=0, n=5, k=2 : 0 5 
s=0, n=5, k=3 : 0 3 5 
s=0, n=5, k=4 : 0 2 3 5 
s=0, n=5, k=5 : 0 1 3 4 5 
s=0, n=5, k=6 : 0 1 2 3 4 5 
s=0, n=6, k=2 : 0 6 
s=0, n=6, k=3 : 0 3 6 
s=0, n=6, k=4 : 0 2 4 6 
s=0, n=6, k=5 : 0 2 3 5 6 
s=0, n=6, k=6 : 0 1 2 4 5 6 
s=0, n=6, k=7 : 0 1 2 3 4 5 6 
s=0, n=7, k=2 : 0 7 
s=0, n=7, k=3 : 0 4 7 
s=0, n=7, k=4 : 0 2 5 7 
s=0, n=7, k=5 : 0 2 4 5 7 
s=0, n=7, k=6 : 0 1 3 4 6 7 
s=0, n=7, k=7 : 0 1 2 4 5 6 7 
s=0, n=7, k=8 : 0 1 2 3 4 5 6 7 
s=0, n=8, k=2 : 0 8 
....
s=4, n=15, k=2 : 4 15 
s=4, n=15, k=3 : 4 10 15 
s=4, n=15, k=4 : 4 8 11 15 
s=4, n=15, k=5 : 4 7 10 12 15 
s=4, n=15, k=6 : 4 6 8 11 13 15 
s=4, n=15, k=7 : 4 6 8 10 11 13 15 
s=4, n=15, k=8 : 4 6 7 9 10 12 13 15 
s=4, n=15, k=9 : 4 5 7 8 10 11 12 14 15 
s=4, n=15, k=10 : 4 5 6 8 9 10 11 13 14 15 
s=4, n=15, k=11 : 4 5 6 7 8 10 11 12 13 14 15 
s=4, n=15, k=12 : 4 5 6 7 8 9 10 11 12 13 14 15 
....
s=4, n=17, k=2 : 4 17 
s=4, n=17, k=3 : 4 11 17 
s=4, n=17, k=4 : 4 8 13 17 
s=4, n=17, k=5 : 4 7 11 14 17 
s=4, n=17, k=6 : 4 7 9 12 14 17 
s=4, n=17, k=7 : 4 6 8 11 13 15 17 
s=4, n=17, k=8 : 4 6 8 10 11 13 15 17 
s=4, n=17, k=9 : 4 6 7 9 11 12 14 15 17 
s=4, n=17, k=10 : 4 5 7 8 10 11 13 14 16 17 
s=4, n=17, k=11 : 4 5 7 8 9 11 12 13 14 16 17 
s=4, n=17, k=12 : 4 5 6 8 9 10 11 12 13 15 16 17 
s=4, n=17, k=13 : 4 5 6 7 8 9 11 12 13 14 15 16 17 
s=4, n=17, k=14 : 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
s=4, n=18, k=2 : 4 18 
s=4, n=18, k=3 : 4 11 18 
s=4, n=18, k=4 : 4 9 13 18 
s=4, n=18, k=5 : 4 8 11 15 18 
s=4, n=18, k=6 : 4 7 10 12 15 18 
s=4, n=18, k=7 : 4 6 9 11 13 16 18 
s=4, n=18, k=8 : 4 6 8 10 12 14 16 18 
s=4, n=18, k=9 : 4 6 8 9 11 13 15 16 18 
s=4, n=18, k=10 : 4 6 7 9 10 12 13 15 16 18 
s=4, n=18, k=11 : 4 5 7 8 10 11 12 14 15 17 18 
s=4, n=18, k=12 : 4 5 7 8 9 10 12 13 14 15 17 18 
s=4, n=18, k=13 : 4 5 6 8 9 10 11 12 13 15 16 17 18 
s=4, n=18, k=14 : 4 5 6 7 8 9 10 12 13 14 15 16 17 18 
s=4, n=18, k=15 : 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
....
s=9, n=10, k=2 : 9 10 
s=9, n=11, k=2 : 9 11 
s=9, n=11, k=3 : 9 10 11 
s=9, n=12, k=2 : 9 12 
s=9, n=12, k=3 : 9 11 12 
s=9, n=12, k=4 : 9 10 11 12 
s=9, n=13, k=2 : 9 13 
s=9, n=13, k=3 : 9 11 13 
s=9, n=13, k=4 : 9 10 12 13 
s=9, n=13, k=5 : 9 10 11 12 13 
s=9, n=14, k=2 : 9 14 
s=9, n=14, k=3 : 9 12 14 
s=9, n=14, k=4 : 9 11 12 14 
s=9, n=14, k=5 : 9 10 12 13 14 
s=9, n=14, k=6 : 9 10 11 12 13 14 
s=9, n=15, k=2 : 9 15 
s=9, n=15, k=3 : 9 12 15 
s=9, n=15, k=4 : 9 11 13 15 
s=9, n=15, k=5 : 9 11 12 14 15 
s=9, n=15, k=6 : 9 10 11 13 14 15 
s=9, n=15, k=7 : 9 10 11 12 13 14 15 
s=9, n=16, k=2 : 9 16 
s=9, n=16, k=3 : 9 13 16 
s=9, n=16, k=4 : 9 11 14 16 
s=9, n=16, k=5 : 9 11 13 14 16 
s=9, n=16, k=6 : 9 10 12 13 15 16 
s=9, n=16, k=7 : 9 10 11 13 14 15 16 
s=9, n=16, k=8 : 9 10 11 12 13 14 15 16 
s=9, n=17, k=2 : 9 17 
s=9, n=17, k=3 : 9 13 17 
s=9, n=17, k=4 : 9 12 14 17 
s=9, n=17, k=5 : 9 11 13 15 17 
s=9, n=17, k=6 : 9 11 12 14 15 17 
s=9, n=17, k=7 : 9 10 12 13 14 16 17 
s=9, n=17, k=8 : 9 10 11 12 14 15 16 17 
s=9, n=17, k=9 : 9 10 11 12 13 14 15 16 17 
s=9, n=18, k=2 : 9 18 
s=9, n=18, k=3 : 9 14 18 
s=9, n=18, k=4 : 9 12 15 18 
s=9, n=18, k=5 : 9 11 14 16 18 
s=9, n=18, k=6 : 9 11 13 14 16 18 
s=9, n=18, k=7 : 9 11 12 14 15 17 18 
s=9, n=18, k=8 : 9 10 12 13 14 15 17 18 
s=9, n=18, k=9 : 9 10 11 12 14 15 16 17 18 
s=9, n=18, k=10 : 9 10 11 12 13 14 15 16 17 18 
s=9, n=19, k=2 : 9 19 
s=9, n=19, k=3 : 9 14 19 
s=9, n=19, k=4 : 9 12 16 19 
s=9, n=19, k=5 : 9 12 14 17 19 
s=9, n=19, k=6 : 9 11 13 15 17 19 
s=9, n=19, k=7 : 9 11 12 14 16 17 19 
s=9, n=19, k=8 : 9 10 12 13 15 16 18 19 
s=9, n=19, k=9 : 9 10 12 13 14 15 17 18 19 
s=9, n=19, k=10 : 9 10 11 12 13 15 16 17 18 19 
s=9, n=19, k=11 : 9 10 11 12 13 14 15 16 17 18 19 
s=9, n=20, k=2 : 9 20 
s=9, n=20, k=3 : 9 15 20 
s=9, n=20, k=4 : 9 13 16 20 
s=9, n=20, k=5 : 9 12 15 17 20 
s=9, n=20, k=6 : 9 11 13 16 18 20 
s=9, n=20, k=7 : 9 11 13 15 16 18 20 
s=9, n=20, k=8 : 9 11 12 14 15 17 18 20 
s=9, n=20, k=9 : 9 10 12 13 15 16 17 19 20 
s=9, n=20, k=10 : 9 10 11 13 14 15 16 18 19 20 
s=9, n=20, k=11 : 9 10 11 12 13 15 16 17 18 19 20 
s=9, n=20, k=12 : 9 10 11 12 13 14 15 16 17 18 19 20 
s=9, n=21, k=2 : 9 21 
s=9, n=21, k=3 : 9 15 21 
s=9, n=21, k=4 : 9 13 17 21 
s=9, n=21, k=5 : 9 12 15 18 21 
s=9, n=21, k=6 : 9 11 14 16 19 21 
s=9, n=21, k=7 : 9 11 13 15 17 19 21 
s=9, n=21, k=8 : 9 11 12 14 16 18 19 21 
s=9, n=21, k=9 : 9 11 12 14 15 17 18 20 21 
s=9, n=21, k=10 : 9 10 12 13 14 16 17 18 20 21 
s=9, n=21, k=11 : 9 10 11 13 14 15 16 17 19 20 21 
s=9, n=21, k=12 : 9 10 11 12 13 14 16 17 18 19 20 21 
s=9, n=21, k=13 : 9 10 11 12 13 14 15 16 17 18 19 20 21 
s=9, n=22, k=2 : 9 22 
s=9, n=22, k=3 : 9 16 22 
s=9, n=22, k=4 : 9 13 18 22 
s=9, n=22, k=5 : 9 12 16 19 22 
s=9, n=22, k=6 : 9 12 14 17 19 22 
s=9, n=22, k=7 : 9 11 13 16 18 20 22 
s=9, n=22, k=8 : 9 11 13 15 16 18 20 22 
s=9, n=22, k=9 : 9 11 12 14 16 17 19 20 22 
s=9, n=22, k=10 : 9 10 12 13 15 16 18 19 21 22 
s=9, n=22, k=11 : 9 10 12 13 14 16 17 18 19 21 22 
s=9, n=22, k=12 : 9 10 11 13 14 15 16 17 18 20 21 22 
s=9, n=22, k=13 : 9 10 11 12 13 14 16 17 18 19 20 21 22 
s=9, n=22, k=14 : 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
s=9, n=23, k=2 : 9 23 
s=9, n=23, k=3 : 9 16 23 
s=9, n=23, k=4 : 9 14 18 23 
s=9, n=23, k=5 : 9 13 16 20 23 
s=9, n=23, k=6 : 9 12 15 17 20 23 
s=9, n=23, k=7 : 9 11 14 16 18 21 23 
s=9, n=23, k=8 : 9 11 13 15 17 19 21 23 
s=9, n=23, k=9 : 9 11 13 14 16 18 20 21 23 
s=9, n=23, k=10 : 9 11 12 14 15 17 18 20 21 23 
s=9, n=23, k=11 : 9 10 12 13 15 16 17 19 20 22 23 
s=9, n=23, k=12 : 9 10 12 13 14 15 17 18 19 20 22 23 
s=9, n=23, k=13 : 9 10 11 13 14 15 16 17 18 20 21 22 23 
s=9, n=23, k=14 : 9 10 11 12 13 14 15 17 18 19 20 21 22 23 
s=9, n=23, k=15 : 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 

Answer 4

If you want the intervals to be as even as possible, consider using a line drawing algorithm such as bresenham's line algorithm, draw a line from point (0,0) to (n,k) and pick the distinct x coordinates.

Answer 5

I would look to get a collection of decimal instead and then handle your conversion back to int however you want:

        int n = 10;
        int k = 5;      // Actually 6

        List<decimal> results = new List<decimal>();

        decimal interval = (decimal)n / (decimal)k;
        for (int i = 0; i <= k ; i++)
        {
            results.Add(interval * (decimal)i);
        }

You will see I use k=5 to return the results for 6.