Algorithm to break up a vector

**Michael Mair** · Nov 14 '05, 04:13 PM

Re: Algorithm to break up a vector

No Such Luck wrote:[color=blue]
> 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.[/color]

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.programmin g 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.

[color=blue]
> 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?[/color]

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
--
E-Mail: Mine is a gmx dot de address.

**Eric Sosman** · Nov 14 '05, 04:13 PM

Re: Algorithm to break up a vector

No Such Luck wrote:[color=blue]
> 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[/color]

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>

--
Eric.Sosman@sun .com

**No Such Luck** · Nov 14 '05, 04:13 PM

Re: Algorithm to break up a vector

"Eric Sosman" <eric.sosman@su n.com> wrote in message
news:cpah08$q49 $1@news1brm.Cen tral.Sun.COM...[color=blue]
> No Such Luck wrote:[color=green]
>> 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[/color]
>
> 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>[/color]

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** · Nov 14 '05, 04:20 PM

Re: Algorithm to break up a vector

"No Such Luck" <no@such.luck > wrote in message
news:BZWdndiC76 vOlSTcRVn-iw@rcn.net...[color=blue]
> Thanks, Eric. I will give this implementation a whirl tomorrow. A divide[/color]
and[color=blue]
> conquer technique never occurred to me.[/color]

It should have. :-)

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

-Mike

**Lawrence Kirby** · Nov 14 '05, 04:26 PM

Re: Algorithm to break up a vector

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

....
[color=blue][color=green][color=darkred]
>>> 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:[/color][/color][/color]

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.
[color=blue][color=green][color=darkred]
>>> 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[/color]
>>
>> 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.[/color][/color]

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
[color=blue][color=green]
>> Its principal virtue is that it's easy to see
>> why it works, and hence hard to get wrong.[/color][/color]

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.
[color=blue][color=green]
>> <off-topic>
>>
>> It's also an illustrative example of a divide-and-conquer
>> solution that *doesn't* beg for a recursive implementation.[/color][/color]

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.
[color=blue][color=green]
>> </off-topic>[/color]
>
> 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...[/color]

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\ntes ttotal=%d\n", testtotal);
}

Lawrence

**No Such Luck** · Nov 14 '05, 04:26 PM

Re: Algorithm to break up a vector

Lawrence Kirby wrote:[color=blue]
> On Thu, 09 Dec 2004 21:22:08 -0500, No Such Luck wrote:
>
> ...
>[color=green][color=darkred]
> >>> The obvious solution to the above example be to have 3 subvectors[/color][/color][/color]
of[color=blue][color=green][color=darkred]
> >>> size 7, and 4 subvectors of size 6, but I'm having a hard time[/color][/color][/color]
thinking[color=blue][color=green][color=darkred]
> >>> of a way to implement this for an arbitrary vector size and[/color][/color][/color]
number of[color=blue][color=green][color=darkred]
> >>> subvectors. I know the mod(%) operator is probably required, and[/color][/color][/color]
I know[color=blue][color=green][color=darkred]
> >>> for the above example that the algorithm I need will result:[/color][/color]
>
> 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[/color]
do.[color=blue]
>[color=green][color=darkred]
> >>> 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 >[/color][/color][/color]
0;[color=blue][color=green][color=darkred]
> >> --subcount) {
> >> subsizes[subcount-1] =
> >> (2 * vecsize + subcount) / (2 * subcount);
> >> vecsize -= subsizes[subcount-1];
> >> }
> >> }
> >> (That mess in the middle is merely "vecsize / subcount, rounded."[/color][/color][/color]
You[color=blue][color=green][color=darkred]
> >> could use an ordinary integer division or a "ceiling" without[/color][/color][/color]
affecting[color=blue][color=green][color=darkred]
> >> the validity of the method, but you'd get a different pattern of[/color][/color][/color]
long[color=blue][color=green][color=darkred]
> >> and short sub-vectors.)
> >>
> >> This method will balance the sub-vector lengths as
> >> evenly as is possible.[/color][/color]
>
> 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
>[color=green][color=darkred]
> >> Its principal virtue is that it's easy to see
> >> why it works, and hence hard to get wrong.[/color][/color]
>
> 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[/color]
uneven[color=blue]
> distribution indicates. Essentially it creates a non-linear
> convergence.[/color]

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** · Nov 14 '05, 04:27 PM

Re: Algorithm to break up a vector

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

....
[color=blue][color=green]
>> 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[/color]
> uneven[color=green]
>> distribution indicates. Essentially it creates a non-linear
>> convergence.[/color]
>
> It works perfectly. I have implemented it and tried in on thousands of
> variations of vecsize and subcount, all with correct results. And it[/color]

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.
[color=blue]
> 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.[/color]

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** · Nov 14 '05, 04:27 PM

Re: Algorithm to break up a vector

Lawrence Kirby wrote:[color=blue]
> On Wed, 15 Dec 2004 13:20:21 -0800, No Such Luck wrote:
>
> ...
>[color=green][color=darkred]
> >> 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[/color]
> > uneven[color=darkred]
> >> distribution indicates. Essentially it creates a non-linear
> >> convergence.[/color]
> >
> > It works perfectly. I have implemented it and tried in on thousands[/color][/color]
of[color=blue][color=green]
> > variations of vecsize and subcount, all with correct results. And[/color][/color]
it[color=blue]
>
> I'm not saying it doesn't work, I'm pretty sure that it does. My[/color]
question[color=blue]
> is whether you can PROVE that it is correct. What you have done is[/color]
good[color=blue]
> verification but unless you have tested EVERY possible variation it[/color]
isn't[color=blue]
> proof.[/color]

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** · Nov 14 '05, 04:28 PM

Re: Algorithm to break up a vector

On 16 Dec 2004 10:49:33 -0800, in comp.lang.c , "No Such Luck"
<no_suchluck@ho tmail.com> wrote:
[color=blue]
>
>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).[/color]

This isn't proof tho, its empirical evidence. A similar huge body of
evidence exists to support Newton's laws. They're wrong.
[color=blue]
>What proof are you looking for?[/color]

You seem to be trying to prove an algo. I'd suggest a mathematical method.
[color=blue]
>Something like:
>
>for (vecsize = 1; vecsize < 1000000; vecsize++)
>{
>for (subcount = 1; soubcount < 1000000; subcount++)
>{
> test_algorithm( vecsize, subcount);
> }
>}[/color]

Thats still empirical.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt >

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

**Richard Harter** · Nov 14 '05, 04:28 PM

Re: Algorithm to break up a vector

On 9 Dec 2004 12:47:36 -0800, "No Such Luck" <no_suchluck@ho tmail.com>
wrote:
[color=blue]
>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?[/color]

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, cri@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** · Nov 14 '05, 04:29 PM

Re: Algorithm to break up a vector

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

....
[color=blue]
> 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;[/color]

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** · Nov 14 '05, 04:29 PM

Re: Algorithm to break up a vector

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

....
[color=blue][color=green]
>> I'm not saying it doesn't work, I'm pretty sure that it does. My[/color]
> question[color=green]
>> is whether you can PROVE that it is correct. What you have done is[/color]
> good[color=green]
>> verification but unless you have tested EVERY possible variation it[/color]
> isn't[color=green]
>> proof.[/color]
>
> 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:[/color]

....

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

Algorithm to break up a vector

Algorithm to break up a vector

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment