Prediction Algorithm

[anantmf]

Hi,

Is there any algorithm available such that given set of N numbers, it can predict the N+1 number ?
Please let me know about it, and if there is a implementation in C/C++ or any other language please let me know.

Regards,
Anant.

[anantmf]

Thanks in advance.

[MXP]

What kind of predication are you looking for? What if the set of N numbers is generated with rand()? What kind of set are we looking at?

[anantmf]

Yes, it may be generated with rand(), but for the algorithm it is completely unknown. It should be able to learn the sequence based on the given set of data. and we are looking at the set of pure integers from 0 to 100.

[Alvaro]

This is my function:

Code: Select all

int next_number(std::vector<int> const &) {
  return 50;
}

If you don't like it, what don't you like about it?

[Wizard]

No. This is an impossible problem. If the numbers are patterned, then you can develop an AI (genetic programming, etc...) to find that pattern and predict the next number, but if there is no number, it's an exercise in futility.
Not that such exercises aren't fun: I wrote just such an AI a couple years ago to see if it could find a pattern in the lotto numbers. It took 4 years of numbers, and spent almost 3 days processing, and came up with nothing. Ah well, it was an amusing afternoon of coding.

[ventsyv]

That reminds me of when I studied polynomial curve fitting in college. You have a bunch of points and you are trying to find the best curve to those points, basically find a formula that describes how those points have been generated.
Still that's probably very limited and would not work on randomly generated numbers.

[Alvaro]

There is a theoretical framework where the problem does make sense. Consider some formal language (lambda calculus, Turing machines... something like that) in which we can describe programs that spit out infinite sequences of numbers. Now given a finite sequence of numbers, consider all the programs that spit out sequences that start with those numbers. Pick the shortest one, and use it to predict what the next number will be. Almost equivalently, you can say that the next number is the one that would make the sequence have the smallest Kolmogorov complexity.

If you think up a rule that generates numbers, this method will eventually find it, if you give it enough data points.

Of course this method is a nice little theory but doesn't work in practice. You run into the halting problem and that type of nasty things.

[saeed84]

is it possible that what you looking for is related to sorting algorithms?