P: n/a

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.  
Share this Question
P: n/a

No Such Luck 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.
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
7776666 instead of 6767676.
Hints:
45/7 = 6
45%7 = 3
Cheers
Michael

EMail: Mine is a gmx dot de address.  
P: n/a

No Such Luck 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)(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 subvectors desired;
int subsizes[subcount];
for ( ; subcount > 0; subcount) {
subsizes[subcount1] =
(2 * vecsize + subcount) / (2 * subcount);
vecsize = subsizes[subcount1];
}
(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
subvectors.)
This method will balance the subvector 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.
<offtopic>
It's also an illustrative example of a divideandconquer
solution that *doesn't* beg for a recursive implementation.
</offtopic>
 Er*********@sun.com  
P: n/a

"Eric Sosman" <er*********@sun.com> wrote in message
news:cp**********@news1brm.Central.Sun.COM... No Such Luck 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)(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 subvectors desired; int subsizes[subcount]; for ( ; subcount > 0; subcount) { subsizes[subcount1] = (2 * vecsize + subcount) / (2 * subcount); vecsize = subsizes[subcount1]; }
(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 subvectors.)
This method will balance the subvector 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.
<offtopic>
It's also an illustrative example of a divideandconquer solution that *doesn't* beg for a recursive implementation.
</offtopic>
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...  
P: n/a

"No Such Luck" <no@such.luck> wrote in message
news:BZ********************@rcn.net... 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  
P: n/a

On Thu, 09 Dec 2004 21:22:08 0500, No Such Luck wrote:
.... 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:
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 subvectors desired; int subsizes[subcount]; for ( ; subcount > 0; subcount) { subsizes[subcount1] = (2 * vecsize + subcount) / (2 * subcount); vecsize = subsizes[subcount1]; } } (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 subvectors.)
This method will balance the subvector 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
Its principal virtue is that it's easy to see why it works, and hence hard to get wrong.
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 nonlinear
convergence.
<offtopic>
It's also an illustrative example of a divideandconquer solution that *doesn't* beg for a recursive implementation.
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.
</offtopic>
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, subcount1, (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  
P: n/a

Lawrence Kirby wrote: On Thu, 09 Dec 2004 21:22:08 0500, No Such Luck wrote:
...
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: 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 subvectors desired; int subsizes[subcount]; for ( ; subcount >
0; subcount) { subsizes[subcount1] = (2 * vecsize + subcount) / (2 * subcount); vecsize = subsizes[subcount1]; } } (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 subvectors.)
This method will balance the subvector 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 Its principal virtue is that it's easy to see why it works, and hence hard to get wrong. 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 nonlinear 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.  
P: n/a

On Wed, 15 Dec 2004 13:20:21 0800, No Such Luck wrote:
.... 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 nonlinear 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
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');
}  
P: n/a

Lawrence Kirby wrote: On Wed, 15 Dec 2004 13:20:21 0800, No Such Luck wrote:
...
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 nonlinear 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 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);
}
}  
P: n/a

On 16 Dec 2004 10:49:33 0800, in comp.lang.c , "No Such Luck"
<no*********@hotmail.com> 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).
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.

Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/Cfaq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
== Posted via Newsfeeds.Com  UnlimitedUncensoredSecure Usenet News== http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
= East and WestCoast Server Farms  Total Privacy via Encryption =  
P: n/a

On 9 Dec 2004 12:47:36 0800, "No Such Luck" <no*********@hotmail.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)(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 Mr 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 = Nq*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  
P: n/a

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 Mr 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 = Nq*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  
P: n/a

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%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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 2553
 replies: 12
 date asked: Nov 14 '05
