|
What about the brutal approach
#include <stdio.h>
void main()
{
int n;
int i,j,k,l;
n=0;
for (i = 0; i <= 10; i++)
for (j = 0; j <= 10; j++)
for (k = 0; k <= 10; k++)
for (l = 0; l <= 10; l++)
if ( i + j + k + l == 10)
{
printf("%d [%d, %d, %d, %d]\n", n++, i,j,k,l);
}
}
I know it's a waste of cycles...
(And actually I don't know even if it is correct  )
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
CPallini wrote: (And actually I don't know even if it is correct )
You must therefore come up with a separate program to verify the output of this one.
"Normal is getting dressed in clothes that you buy for work and driving through traffic in a car that you are still paying for, in order to get to the job you need to pay for the clothes and the car and the house you leave vacant all day so you can afford to live in it." - Ellen Goodman
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
|
|
|
|
|
That was going on my arrogant assumptions: of course the proof (whatever it will be, not necessary another program) it's left to the OP.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
Incidently, correctness proof is very simple (if I'm right).
Since the approach (i.e. brute force), the code enumerates all possible sequences (base 11 notation  ):
0000
0001
0002
....
000A
0010
....
00AA
0100
....
AAAA
selecting only the ones summing up to A. Hence it exaustive and each selected sequence is unique.
Off course it is not a formal proof, but you get the idea.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
This is just an awkward way of phrasing a standard combinatorial problem.
Think of your numbers as little rods (some of zero length), now in each combination lay out the rods end to end, note that they combine to length 1. Note that the combination can be expressed by simply listing the finishing locations of each rod, and these occur on the boundaries of the M subintervals.
If you consider the interval [0,1] broken into M subintervals, what you have to do is to enumerate how many ways you can allocate N items into M+1 boxes. Each box is the end of an interval. So if M=10 and one allocation goes {1,2,0,1..} then your numbers are {0, 0.1, 0, 0.2, ..}. They are guaranteed to add to 1 by construction.
The algorithm is probably most easily implemented recursively.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: Think of your numbers as little rods
Does that really help you? 
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
No it didn't help me, I added it last thing when I thought my description looked a bit abstract. When I added is I was thinking of cuisenaire rods (link[^]), but others may not know what they are.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Thank you for bringing up Georges Cuisenaire, a former Belgian teacher;
I vaguely remember having seen, maybe even used, such rods in elementary school,
but nowadays I am pretty sure calculators and computers have eradicated them.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
They didn't help me much at school either, but I did like building things with them. In fact I think that this is probably the first time I have used/referred to them for about 40 years. They're not perfect here, they don't have zero length rods.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: They're not perfect here, they don't have zero length rods
Don't worry, I have an infinite supply ..
I'm largely language agnostic
After a while they all bug me 
|
|
|
|
|
Thanks Peter. You are correct, it turned out to be a standard combinatorial problem as you suggested. It was late and my brain was functioning sub-optimally 
|
|
|
|
|
And if you make the lengths unique, you get a Golomb ruler.
There are II kinds of people in the world, those who understand binary and those who understand Roman numerals. Web - Blog - RSS - Math
|
|
|
|
|
If 'yes' answers to a 'yes'-or-'no' question can be verified "quickly" (in polynomial time), can the answers themselves also be computed quickly?
Richard of York gave battle in vain.
|
|
|
|
|
The answer is: not necessarily. For example, in mathematics there is a class of proofs called "existence proofs" that show an answer exists, but don't give the answer.
Prime factorization comes to mind. We can answer "yes" to the question of whether a large number can be expressed as a product of primes. Computing those primes, however, can be extremely difficult.
|
|
|
|
|
Alan Balkany wrote: Computing those primes, however, can be extremely difficult.
Thankfully, this is very difficult. Our current encryption algorithms depend on it.
|
|
|
|
|
See also the subset-sum problem...
|
|
|
|
|
Hi guys...I am from Bangladesh and my knowledge is very limited.I have developed an algorithm using which any data can be hidden in a text file.After hiding the data in the text file,the size of the text file remains absolutely unchanged and there is no change whatsoever in the file's content as far as reading the file is concerned.I know there r lots of data hiding techniques.Guys can you plse tell me if this techniq has already been implemented the way i have done it...I mean hiding the data in a text file without changing the file size even by a single byte and you wont see a single replacement/change/distortion in any of the letters of the file.As far as reading the file is concerned...the file will remain 100% unchanged even after hiding the data in it.
modified on Tuesday, March 18, 2008 8:42 PM
|
|
|
|
|
Let me get this right. Your algorithm hides data in a file but doesn't alter the file in any way?
Does it look anything like this?
Paul Marfleet
"No, his mind is not for rent
To any God or government"
Tom Sawyer - Rush
|
|
|
|
|
Hiding information in text, isn't that what documentation is about?
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
It hides the data in a file and it does not change the file size and no visible change whatsoever in the file.
|
|
|
|
|
Your original post states 'the file will remain 100% unchanged'. If you're not changing the file, how can you be hiding data in it? What you're saying just doesn't make sense.
Paul Marfleet
"No, his mind is not for rent
To any God or government"
Tom Sawyer - Rush
|
|
|
|
|
I said 100% unchanged as far ar reading the file is concerned.
|
|
|
|
|
Pallab_GT wrote: I said 100% unchanged as far ar reading the file is concerned.
How can you make this claim? In order to hide the data, you are going to have to modify some characters in the file. If I use a diff tool to compare the old and new versions of the file, it's going to flag up some differences. If you make changes to a file, they're going to be noticed.
Paul Marfleet
"No, his mind is not for rent
To any God or government"
Tom Sawyer - Rush
|
|
|
|
|
pmarfleet wrote: How can you make this claim? In order to hide the data, you are going to have to modify some characters in the file. If I use a diff tool to compare the old and new versions of the file, it's going to flag up some differences. If you make changes to a file, they're going to be noticed.
You're wrong.
You wrote all the above because you're not aware of occultism superanatural powers.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
You read it wrong.I said AS FAR AS READING THE FILE IS CONCERNED,the file remains 100% unmodified.Ofcourse i have to make some modification but that does not affect the size of the file or for that matter the readability of the file even by a bit.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
