Algorithm to break up a vector

[No Such Luck]

Hi All:

I'm not sure if this is the right place to ask this question, but I
couldn't find a more appropriate group. This is more of a theory
question regarding an algorithm implemented in C, not necessarily a C
language question.

I'm trying to break up a vector into an arbitrary number of subvectors,
equal (or as near to equal) in size as possible. My problem occurs when
the vector is not evenly divisible by the number of subvectors (i.e.,
vector length: 45, number of subvectors: 7)

If I break up the vector based on (int)(vectorsiz e/numsubvectors), not
all of the original vector data will be included. If I break up the
vector based on ceil(vectorsize/numsubvectors), the end of the vector
will be passed, resulting in a memory violation.

The obvious solution to the above example be to have 3 subvectors of
size 7, and 4 subvectors of size 6, but I'm having a hard time thinking
of a way to implement this for an arbitrary vector size and number of
subvectors. I know the mod(%) operator is probably required, and I know
for the above example that the algorithm I need will result:

Subvector 1: Size 6
Subvector 2: Size 7
Subvector 3: Size 6
Subvector 4: Size 7
Subvector 5: Size 6
Subvector 6: Size 7
Subvector 7: Size 6

Anyone have any ideas?

Thanks.

[Richard Harter]

On 9 Dec 2004 12:47:36 -0800, "No Such Luck" <no*********@ho tmail.com>
wrote:

Hi All:

I'm not sure if this is the right place to ask this question, but I
couldn't find a more appropriate group. This is more of a theory
question regarding an algorithm implemented in C, not necessarily a C
language question.

I'm trying to break up a vector into an arbitrary number of subvectors,
equal (or as near to equal) in size as possible. My problem occurs when
the vector is not evenly divisible by the number of subvectors (i.e.,
vector length: 45, number of subvectors: 7)

If I break up the vector based on (int)(vectorsiz e/numsubvectors), not
all of the original vector data will be included. If I break up the
vector based on ceil(vectorsize/numsubvectors), the end of the vector
will be passed, resulting in a memory violation.

The obvious solution to the above example be to have 3 subvectors of
size 7, and 4 subvectors of size 6, but I'm having a hard time thinking
of a way to implement this for an arbitrary vector size and number of
subvectors. I know the mod(%) operator is probably required, and I know
for the above example that the algorithm I need will result:

Subvector 1: Size 6
Subvector 2: Size 7
Subvector 3: Size 6
Subvector 4: Size 7
Subvector 5: Size 6
Subvector 6: Size 7
Subvector 7: Size 6

Anyone have any ideas?

I must be missing something. If N is the number of elements in the
vector and M is the number of desired subvectors, divide M into N
getting the quotient and remainder. Let them be q and r. Then r of
the M subvectors have length q+1 and M-r have length q. Mix them up
any way you like. Since this is comp.lang.c it might be nice to have
some C code:

q = N/M;
r = N-q*M;
Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
I started out in life with nothing
I still have most of it left

[Lawrence Kirby]

On Fri, 17 Dec 2004 10:03:43 +0000, Richard Harter wrote:

....

I must be missing something. If N is the number of elements in the
vector and M is the number of desired subvectors, divide M into N
getting the quotient and remainder. Let them be q and r. Then r of
the M subvectors have length q+1 and M-r have length q. Mix them up
any way you like. Since this is comp.lang.c it might be nice to have
some C code:

q = N/M;
r = N-q*M;

Both of the code examples I posted in effect use this method, although you
can of course write the 2nd as r = N%M;

Eric's method is interesting though becasue it uses a fundamentally
different approach.

Lawrence

[Lawrence Kirby]

On Thu, 16 Dec 2004 10:49:33 -0800, No Such Luck wrote:

....

I'm not saying it doesn't work, I'm pretty sure that it does. My

question

is whether you can PROVE that it is correct. What you have done is

good

verification but unless you have tested EVERY possible variation it

isn't

proof.

Like I said, I've tested Eric's algorithm on hundreds of vecsizes
ranging from 100 to 1500, and subcounts ranging from 1 to 100 (i.e.,
thousands of trials). All with correct results (all verified
numerically, and some verified visually).

What proof are you looking for? Something like:

....

No, proof of the correctness of the algorithm. Maybe something
like following outline:

Initially there are subcount subvectors to define over vecsize elements.
Each final subvector can have size S where S is either vecsize/subcount or
vecsize/subcount+1.

Let T be the total number of subvectors remaining
to allocate. Initially T=subcount

Let N be the number of subvectors of size vecsize/subcount+1
remaining to allocate. Initially N=vecsize%subco unt.

Each iteration of the loop reduces T by 1 until it reaches 0, and reduces
N by 0 or 1 depending on a calculation in the loop. The algorithm is
correct if it maintains the relation 0 <= N <= T at every iteration. In
particular this means that N is 0 when the loop terminates.

Lawrence