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)(vectorsize/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.

 

[Michael Mair]

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.

If you give us C code to work with, then we will point out
possible algorithmic shortcomings.
A request for a C algorithm is not topical here.
comp.programming might be a good starting point to ask for
an algorithm. Then you can implement it -- and if you have
problems because your program does not run as intended,
then you can isolate a minimal running program exhibiting
these problems and we will help you.

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)(vectorsize/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?

Yes. This sounds like an idiotic homework question. More natural
would be to give the maximum length of subvectors and to go for
7|7|7|6|6|6|6 instead of 6|7|6|7|6|7|6.

Hints:
45/7 = 6
45%7 = 3


Cheers
Michael

 

[Eric Sosman]

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)(vectorsize/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

An easy way to proceed is (pseudocode):

int vecsize = length of original vector;
int subcount = number of sub-vectors desired;
int subsizes[subcount];
for ( ; subcount > 0; --subcount) {
subsizes[subcount-1] =
(2 * vecsize + subcount) / (2 * subcount);
vecsize -= subsizes[subcount-1];
}

(That mess in the middle is merely "vecsize / subcount,
rounded." You could use an ordinary integer division or
a "ceiling" without affecting the validity of the method,
but you'd get a different pattern of long and short
sub-vectors.)

This method will balance the sub-vector lengths as
evenly as is possible. Its principal virtue is that it's
easy to see why it works, and hence hard to get wrong.

<off-topic>

It's also an illustrative example of a divide-and-conquer
solution that *doesn't* beg for a recursive implementation.

</off-topic>

 

[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)(vectorsize/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

An easy way to proceed is (pseudocode):

int vecsize = length of original vector;
int subcount = number of sub-vectors desired;
int subsizes[subcount];
for ( ; subcount > 0; --subcount) {
subsizes[subcount-1] =
(2 * vecsize + subcount) / (2 * subcount);
vecsize -= subsizes[subcount-1];
}

(That mess in the middle is merely "vecsize / subcount,
rounded." You could use an ordinary integer division or
a "ceiling" without affecting the validity of the method,
but you'd get a different pattern of long and short
sub-vectors.)

This method will balance the sub-vector lengths as
evenly as is possible. Its principal virtue is that it's
easy to see why it works, and hence hard to get wrong.

<off-topic>

It's also an illustrative example of a divide-and-conquer
solution that *doesn't* beg for a recursive implementation.

</off-topic>

Thanks, Eric. I will give this implementation a whirl tomorrow. A divide and
conquer technique never occurred to me. I thought I would have to determine
the size of all the subvectors in the outset...

 

[Mike Wahler]

Thanks, Eric. I will give this implementation a whirl tomorrow. A divide and
conquer technique never occurred to me.

It should have.

'Divide and conquer' is one of the cornerstones of programming,
in any language.

-Mike

 

[Lawrence Kirby]

On Thu, 09 Dec 2004 21:22:08 -0500, No Such Luck wrote:

....

You can do this using modulo arithmetic and I give some example code
below. It doesn't use % to perform the modulo arithmetic but it could do.

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

An easy way to proceed is (pseudocode):

int vecsize = length of original vector; int subcount = number of
sub-vectors desired; int subsizes[subcount]; for ( ; subcount > 0;
--subcount) {
subsizes[subcount-1] =
(2 * vecsize + subcount) / (2 * subcount);
vecsize -= subsizes[subcount-1];
}
}
(That mess in the middle is merely "vecsize / subcount, rounded." You
could use an ordinary integer division or a "ceiling" without affecting
the validity of the method, but you'd get a different pattern of long
and short sub-vectors.)

This method will balance the sub-vector lengths as
evenly as is possible.

It doesn't distribute them evenly. For example with vecsize=45 and
subcount=14 I get subvectors from it like this:

3 4 3 4 3 4 3 3 3 3 3 3 3 3

I can see that it probably works, but I haven't proved it to my
satisfaction yet. This isn't as simple as it first looks as the uneven
distribution indicates. Essentially it creates a non-linear
convergence.

If this qualifies as a divide and conquer algorithm it is a degenerate
one, more a lop one off the end and conquer. You might just as well
say that a linear search (as well as many simple loops) is divide and
conquer because you can test the first (or last) element and then if
necessary do a linear search on the rest. Compare that to a binary search.

Thanks, Eric. I will give this implementation a whirl tomorrow. A divide
and conquer technique never occurred to me. I thought I would have to
determine the size of all the subvectors in the outset...

Try this. It does produce an even (or as even as possible) distribution of
subvector sizes, although a small amount of bias can be controlled by the
initial value of sum. It doesn't write the results to an array but you can
do so easily if you want. With vecsize=45 and subcount=14 it produces

3 3 4 3 3 3 4 3 3 3 3 4 3 3


static void subsizes(int vecsize, int subcount)
{
int basesize = vecsize / subcount;
int bumps = vecsize % subcount;
int sum = subcount/2; /* Try also 0, subcount-1, (subcount+1)/2 */
int testtotal = 0; /* For checking only */
int i;

for (i = 0; i < subcount; i++) {
int subsize = basesize;

if ((sum += bumps) >= subcount) {
sum -= subcount;
subsize++;
}

printf(" %d", subsize);
testtotal += subsize;
}

printf("\n\ntesttotal=%d\n", testtotal);
}

Lawrence

 

[No Such Luck]

On Thu, 09 Dec 2004 21:22:08 -0500, No Such Luck wrote:

...

You can do this using modulo arithmetic and I give some example code
below. It doesn't use % to perform the modulo arithmetic but it could do.

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

An easy way to proceed is (pseudocode):

int vecsize = length of original vector; int subcount = number of
sub-vectors desired; int subsizes[subcount]; for ( ; subcount > 0;
--subcount) {
subsizes[subcount-1] =
(2 * vecsize + subcount) / (2 * subcount);
vecsize -= subsizes[subcount-1];
}
}
(That mess in the middle is merely "vecsize / subcount, rounded." You
could use an ordinary integer division or a "ceiling" without affecting
the validity of the method, but you'd get a different pattern of long
and short sub-vectors.)

This method will balance the sub-vector lengths as
evenly as is possible.

It doesn't distribute them evenly. For example with vecsize=45 and
subcount=14 I get subvectors from it like this:

3 4 3 4 3 4 3 3 3 3 3 3 3 3

I can see that it probably works, but I haven't proved it to my
satisfaction yet. This isn't as simple as it first looks as the uneven
distribution indicates. Essentially it creates a non-linear
convergence.

It works perfectly. I have implemented it and tried in on thousands of
variations of vecsize and subcount, all with correct results. And it
doesn't matter that the distribution of subsizes is uneven. The only
stipulation is that the sizes of all the subvectors are either n or
n+1, and that their sum is the original vecsize.

 

[Lawrence Kirby]

On Wed, 15 Dec 2004 13:20:21 -0800, No Such Luck wrote:

....

It works perfectly. I have implemented it and tried in on thousands of
variations of vecsize and subcount, all with correct results. And it

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.

doesn't matter that the distribution of subsizes is uneven. The only
stipulation is that the sizes of all the subvectors are either n or
n+1, and that their sum is the original vecsize.

In which case you can solve this very simply, for example

static void subsizes2(int vecsize, int subcount)
{
int basesize = vecsize / subcount;
int bumps = vecsize % subcount;
int i;

for (i = 0; i < subcount; i++) {
printf(" %d", basesize + (i < bumps));
}

putchar('\n');
}

 

[No Such Luck]

On Wed, 15 Dec 2004 13:20:21 -0800, No Such Luck wrote:

...
it

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:

for (vecsize = 1; vecsize < 1000000; vecsize++)
{
for (subcount = 1; soubcount < 1000000; subcount++)
{
test_algorithm(vecsize, subcount);
}
}

 

[Mark McIntyre]

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).

This isn't proof tho, its empirical evidence. A similar huge body of
evidence exists to support Newton's laws. They're wrong.

What proof are you looking for?

You seem to be trying to prove an algo. I'd suggest a mathematical method.

Something like:

for (vecsize = 1; vecsize < 1000000; vecsize++)
{
for (subcount = 1; soubcount < 1000000; subcount++)
{
test_algorithm(vecsize, subcount);
}
}

Thats still empirical.

 

[Richard Harter]

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)(vectorsize/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, (e-mail address removed)
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:

....

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%subcount.

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