Re: Interesting Programming Problem

Tech-Archive recommends: Fix windows errors by optimizing your registry

"Jeff Grippe" <jeff@xxxxxxxxx> wrote:


"Gene Wirchenko" <genew@xxxxxxxx> wrote in message
news:qsor34thvsfn41m5sisqaivomcs84dimv0@xxxxxxxxxx
"Jeff Grippe" <jeff@xxxxxxxxx> wrote:

[snip]

I see your point here but I'm dealing with a relatively small number of
numbers. Of course once you say that you immediately get someone who wants
to use your application with a large data set.

You are dealing with factorials here. They get very big very
fast. 10! is well over one million. That makes ten a big number
relatively speaking. How much data do you have?

You do not search, but rather increment indexes. Actually, it
does not get complex. I already outlined the algorithm. It is little
more complicated than nested loops.

Run:
Pick 16. Reject 14, 8, 7, 5. Pick 2. No more data: back off 2. No
more data: back off 16.

Pick 14. Reject 8, 7. Pick 5. Reject 2. No more data: back off 5.
Pick 2. No more data: back off 2. No more data: back off 14.

Your algorithm is still dealing with factorials because in order to reject
the numbers you are rejecting you must consider them. I'm not sure if your
algorithm allows you to not consider higher numbers once you have rejected
them in a pass through the loop. This may be a problem for which the human
brain is better suited.

Higher numbers, once they are incremented past, will not be
considered.

No, not as a general solution. If you accept close
approximations, then possibly.

What I can add to the problem description is:
1. There will always be a solution (although you must code for the "no
solution" case)

Not for the exact sum version.

By the ordering principle, there will always be a best answer. By
your definition (being close), this is a solution.

2. The numbers will all always be positive

Then use my approach.

I'm going to play with your algorithm a bit more a bit more. I've been
wondering if there were some algorithm where you start with the sum of the
data set and then use subtraction to find your answer.

That is isomorphic to my algorithm. Whether you add up to the
desired number and watch for sums too big or subtract from the desired
number and watch for differences less than zero, it is the same
general idea.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
.

Relevant Pages

  • Help with generating a random matrix with row and column constraint
    ... 2)The sum of all the elements in each column should be 100 ... I am trying to write a code to generate the data set in Matlab, but am struck with the algorithm. ...
    (sci.math.num-analysis)
  • Re: Interesting Programming Problem
    ... You are dealing with factorials here. ... I already outlined the algorithm. ... the numbers you are rejecting you must consider them. ... data set and then use subtraction to find your answer. ...
    (microsoft.public.fox.programmer.exchange)
  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Choose k random lines from file
    ... > What, for the algorithm shown above, or for any algorithm? ... Yes, that is an unbiased generator, but I had thought ... >>give less of a bias using an extra float or double ... >>distribution for the sum. ...
    (comp.programming)
  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)