Fast O(1) algorithm to evenly distribute continuous numbers into continuous subdivisions and output-CodePudding

I have a subset of natural numbers specified by a given max number. For example if the given is 7 then the list is

1,2,3,4,5,6,7

Now I am given another input, the number of subdivisions to evenly divide the list. For any remainder, one extra number is added to each subdivision starting from beginning. If this number is 3, then the subdivided list would be

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

Finally a third input, the "subdivision order (between 1 and the subdivision number)" is given. In the above example if the order is 1 then the output is [1,2,3], if the order is 2 then the output is [4,5]

The trivial dumb way would be first do 7/3=2 and calculate the remainder 7-2*3=1, then generate the first group by assigning 1,2 first and then since the first group order is no bigger the remainder, add one element get 1,2,3. Then generate the second group etc.

However it seems to me there must be a way to directly get a middle group without the need to generate all the previous group. i.e. get [6,7] given the input max_num=7, subdivision_num=3, subdivision_order=3 without going through a for loop.

Now the actual subdivision output needed is indicated by only the smallest and the largest number (i.e. the output for 7,3,1 would be 1,3), so the latter would imply a worst case O(1) algorithm while the trivial dumb way has worst case O(n) where n is the subdivision number.

It seems not so hard but I have struggle for a while not able to come up with the "direct O(1)" algorithm. Any help would be appreciated.

CodePudding user response：

If I understand your question correctly, you're given three values

maximum
segments
segment index (one based)

and you want to return the minimum and maximum of the segment range.

Let's work through an example with slightly larger numbers

maximum = 107
segments = 10
segment index = 4

Ok, doing the math

107 (maximum) / 10 (segments) = 10 values in a segment with 7 left over.

So, the first 7 segments have 11 values and the last 3 segments have 10 values. The remainders go in the first segments.

So 3 * 11 = 33. 3 is the zero-based segment index and the first 3 segments have 11 values,

The 4th segment also has 11 values, so you would return 33 1 and 33 11, or 34 and 44. The only "trick" is to make sure that you differentiate between the segments with a remainder and the segments without a remainder.

You need to calculate four numbers. The number of segments with a remainder, the length of the segment with a remainder, the number of segments without a remainder, and the length of the segment without a remainder.

In the example I gave that would be 7 & 11, 3 & 10. Then you add the counts of the prior segments and the count of the wanted segment. You do this with two multiplications.

The first multiplication is the number of remainder segments times the length of the remainder segments. The second multiplication is the number of non-remainder segments times the length of the non-remainder segments.

Again, using the example I gave, that would be

3 * 11   0 * 10 = 33

where 3 is the zero-based segment index, 11 is the length of a remainder segment, 0 is the number of non-remainder segments and 10 is the length of the non-remainder segment.

The complexity is O(1).

CodePudding user response：

Not considering the time to generate the list and assuming branching and arithmetic operations to take constant time, we can do it in O(1).

parts = max_num // subdivisions_num
rems = max_num % subdivisions_num
if subdivision_order < rems:
  startindex = (parts 1) * (subdivision_order - 1)
  length = parts   1
  print(numlist[startindex:startindex length])
else:
  startindex = (parts 1) * rem   parts * (subdivision_order - rem - 1)
  length = parts
  print(numlist[startindex:startindex length])

I think you don't need to divide list into sublist. You can just calculate the start and length of the subarray.

In this case, if ~subdivision_order~ is less than the remainder of ~max_num~ and ~subdivision_num~, you calculate the start index by just multiplying the ~subdivision_order - 1~ (in case of 0-index) with ~max_num // subdivision_num~ and length will be ~max_num // subdivision_num 1~.

CodePudding user response：

Here is an implementation of the algorithm in a JavaScript snippet. You can input the parameters interactively to test it.

function partition(size, partitionCount, partitionPosition) {
    if (partitionCount < 1 || partitionCount > size) return null; // Out of range
    if (partitionPosition < 1 || partitionPosition > partitionCount) return null; // Out of range
    // Get the largest partition size
    let partitionSize = Math.ceil(size / partitionCount);
    // Determine how many partitions are that large
    let largerPartitionCount = partitionCount - (partitionSize - size % partitionSize) % partitionSize;
    // Convert 1-based position to 0-based index
    let partitionIndex = partitionPosition - 1;
    // Derive the first and last value of the requested partition
    let first = partitionIndex * partitionSize   1 - Math.max(0, partitionIndex - largerPartitionCount);
    let last = first   partitionSize - 1 - (partitionIndex >= largerPartitionCount ? 1 : 0);
    return [first, last];
}

// I/O management

let inputs = document.querySelectorAll("input");
let output = document.querySelector("span");

document.addEventListener("change", refresh);

function refresh() {
    let [size, partitionCount, partitionPosition] = Array.from(inputs, input =>  input.value);
    let result = partition(size, partitionCount, partitionPosition);
    output.textContent = JSON.stringify(result);
}

refresh();

input { width: 3em }

Array size: <input type="number" value="7" ><br>
Number of partitions: <input type="number" value="3" ><br>
Partition to return: <input type="number" value="1" ><br>
<br>
Returned partition: <span></span>