<p>Consider an array of bytes.</p>

<p>I want to partition the array, such that the following two conditions hold:</p>

<ol>
<li><p>The number of bytes within each partition (except perhaps the last one) is between L and U, inclusive. Here, L is much smaller than U.</p></li>
<li><p>Given a sub-array (i.e. consecutive bytes) of the main array, partition boundaries within the sub-array can be detected.</p></li>
</ol>

<h2>Example:</h2>

<p>Let the array of bytes be:</p>

<p><img src="https://i.sstatic.net/knQH9.png" alt="array of bytes"></p>

<p>Let L = 2 and U = 4.</p>

<p>The following partitioning satisfies <strong>requirement 1</strong> (red lines depict partition boundaries). Notice that the size of all partitions is between L and U inclusive.</p>

<p><img src="https://i.sstatic.net/y998G.png" alt="partitioned array"></p>

<p>To explain <strong>requirement 2</strong>, assume that the following sub-array is given:</p>

<p><img src="https://i.sstatic.net/uP92H.png" alt="sub-array"></p>

<p>An algorithm satisfying <strong>requirement 2</strong> should be able to correctly identify partition boundaries:</p>

<p><img src="https://i.sstatic.net/oFOU7.png" alt="partitioned sub-array"></p>

<p><strong>PS:</strong> An idea which only satisfies the second requirement is called <a href="http://theory.stanford.edu/~aiken/publications/papers/sigmod03.pdf" rel="nofollow noreferrer">winnowing</a>. It uses a sliding window over the bytes, computes some fingerprint in each window, and then uses another sliding window (the "winnowing" window) over fingerprints, and then selects the boundary to be the byte corresponding to the fingerprint which satisfies some property in each winnowing window.</p>

<p><strong>Edit:</strong> If no such algorithm exists, we can think of some relaxations. The one that best fits my case changes <strong>requirement 1</strong> as follows:</p>

<p>Let p(n) be the fraction of partitions of length n. We want p(n) to follow some bell-shaped distribution with mean $\mu$ and standard deviation $\sigma$. This way, I can reduce $\sigma$ to concentrate the partition lengths around $\mu$.</p>

CC BY-SA 3.0
2015-01-20T10:53:46.403Z
If that given subarray is just a random input without any extra information, then it's not possible to provide such an algorithm, but is it a randomized algorithm fine? Then what is the definition of randomized algorithm for this problem? e.g a randomized algorithm that partitions and then finds the corresponding partition in a given subarray with probability $p$ and with shift distance $d$, where $p=f(U,L,n),d=g(U,L,n)$.
Saeed
CC BY-SA 3.0
2015-01-20T10:56:19.703Z
@Saeed: Could you elaborate why "it's not possible to provide such an algorithm"?
Sadeq Dousti
CC BY-SA 3.0
2015-01-20T11:05:57.520Z
I mean actually it's somehow not deterministic, e.g attach the subarray that you selected to the end of input, and suppose that the partition in the end is not same as the before, then what shall we guess? the first partition or the second partition?
Saeed
CC BY-SA 3.0
2015-01-20T11:08:40.223Z
@Saeed: The idea of "winnowing windows" (as described at the end of my question) solves the issue you just said. It is deterministic, and it works for all possible sub-arrays. The problem with it, however, is that the partition lengths can be as small as 1.
Sadeq Dousti
CC BY-SA 3.0
2015-01-20T11:15:58.563Z
I see, and somehow I can imagine if there were no $L$ or $U$ it was possible to solve it (sounds natural), but exactly because your U,L are just input, I think we need some relaxation, that means e.g we partition with size between L and U with probability $p$, ... I provided another randomized case in my first comment, but if you are looking for exact proof that is not possible to do this (or it's possible), maybe it's better to change a question a little bit and ask if there is such an algorithm (I think, it should not be so hard to provide a concrete counterexample).
Saeed
CC BY-SA 3.0
2015-01-20T11:20:09.267Z
I have to kindly argue that just because "I think we need some relaxation" is not enough to deduce that "that is not possible to do this". If you can prove it rigorously, then I can look for some relaxation. Anyway, an excellent relaxation in my case is that the partition lengths follow a binomial (or any other bell-shaped) distribution, with a given mean and variance.
Sadeq Dousti
CC BY-SA 3.0
2015-01-20T11:21:10.270Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/20383/discussion-between-saeed-and-sadeq-dousti).
Saeed
CC BY-SA 3.0
2015-01-20T14:28:15.243Z
Some clarifications: The sub-array (I call it $A$) must contain exactly 2 boundaries or any number of boundaries $\geq 0$? Are there constraints on the number of elements of $A$? What are the inputs of the algorithm that must calculate the boundaries in $A$? The sub-array $A$ + L,U  + the length of the original array?
Marzio De Biasi
CC BY-SA 3.0
2015-01-20T14:34:53.300Z
@MarzioDeBiasi (1) no, there's no limit on the number of sub-array boundaries. (2) the length of the original array is not given as input to the algorithm.
Sadeq Dousti
CC BY-SA 3.0
2015-01-20T14:36:53.930Z
@SadeqDousti: thanks, can the original array contain repeated elements?
Marzio De Biasi
CC BY-SA 3.0
2015-01-20T14:38:18.900Z
@MarzioDeBiasi you're welcome. Yes, it can contain repeated elements.
Sadeq Dousti
<ds.algorithms><partition-problem>
Array partitioning with limitations on partition size
Sadeq Dousti
# Array partitioning with limitations on partition size

(Asked by: username_0 on 2015-01-20)

Consider an array of bytes.

I want to partition the array, such that the following two conditions hold:

1. The number of bytes within each partition (except perhaps the last one) is between L and U, inclusive. Here, L is much smaller than U.
2. Given a sub-array (i.e. consecutive bytes) of the main array, partition boundaries within the sub-array can be detected.

## Example:

Let the array of bytes be:

![array of bytes](https://i.sstatic.net/knQH9.png)

Let L = 2 and U = 4.

The following partitioning satisfies **requirement 1** (red lines depict partition boundaries). Notice that the size of all partitions is between L and U inclusive.

![partitioned array](https://i.sstatic.net/y998G.png)

To explain **requirement 2**, assume that the following sub-array is given:

![sub-array](https://i.sstatic.net/uP92H.png)

An algorithm satisfying **requirement 2** should be able to correctly identify partition boundaries:

![partitioned sub-array](https://i.sstatic.net/oFOU7.png)

**PS:** An idea which only satisfies the second requirement is called [winnowing](http://theory.stanford.edu/~aiken/publications/papers/sigmod03.pdf). It uses a sliding window over the bytes, computes some fingerprint in each window, and then uses another sliding window (the "winnowing" window) over fingerprints, and then selects the boundary to be the byte corresponding to the fingerprint which satisfies some property in each winnowing window.

**Edit:** If no such algorithm exists, we can think of some relaxations. The one that best fits my case changes **requirement 1** as follows:

Let p(n) be the fraction of partitions of length n. We want p(n) to follow some bell-shaped distribution with mean $\mu$ and standard deviation $\sigma$. This way, I can reduce $\sigma$ to concentrate the partition lengths around $\mu$.

**Tags:** ds.algorithms, partition-problem

> **Comments:**
> **username_1**: If that given subarray is just a random input without any extra information, then it's not possible to provide such an algorithm, but is it a randomized algorithm fine? Then what is the definition of randomized algorithm for this problem? e.g a randomized algorithm that partitions and then finds the corresponding partition in a given subarray with probability $p$ and with shift distance $d$, where $p=f(U,L,n),d=g(U,L,n)$.  
> **username_0**: @username_1: Could you elaborate why "it's not possible to provide such an algorithm"?  
> **username_1**: I mean actually it's somehow not deterministic, e.g attach the subarray that you selected to the end of input, and suppose that the partition in the end is not same as the before, then what shall we guess? the first partition or the second partition?  
> **username_0**: @username_1: The idea of "winnowing windows" (as described at the end of my question) solves the issue you just said. It is deterministic, and it works for all possible sub-arrays. The problem with it, however, is that the partition lengths can be as small as 1.  
> **username_1**: I see, and somehow I can imagine if there were no $L$ or $U$ it was possible to solve it (sounds natural), but exactly because your U,L are just input, I think we need some relaxation, that means e.g we partition with size between L and U with probability $p$, ... I provided another randomized case in my first comment, but if you are looking for exact proof that is not possible to do this (or it's possible), maybe it's better to change a question a little bit and ask if there is such an algorithm (I think, it should not be so hard to provide a concrete counterexample).  
> **username_0**: I have to kindly argue that just because "I think we need some relaxation" is not enough to deduce that "that is not possible to do this". If you can prove it rigorously, then I can look for some relaxation. Anyway, an excellent relaxation in my case is that the partition lengths follow a binomial (or any other bell-shaped) distribution, with a given mean and variance.  
> **username_1**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/20383/discussion-between-saeed-and-sadeq-dousti).  
> **username_2**: Some clarifications: The sub-array (I call it $A$) must contain exactly 2 boundaries or any number of boundaries $\geq 0$? Are there constraints on the number of elements of $A$? What are the inputs of the algorithm that must calculate the boundaries in $A$? The sub-array $A$ + L,U  + the length of the original array?  
> **username_0**: @MarzioDeBiasi (1) no, there's no limit on the number of sub-array boundaries. (2) the length of the original array is not given as input to the algorithm.  
> **username_2**: @SadeqDousti: thanks, can the original array contain repeated elements?  
> **username_0**: @MarzioDeBiasi you're welcome. Yes, it can contain repeated elements.  

---

## 0 answers

