Need help on an algorithm

Question

I need help on an algorithm. I have randomly generated numbers with 6 digits. Like;

123654 109431

There are approximately 1 million of them saved in a file line by line. I have to filter them according to the rule I try to describe below.

Take a number, compare it to all others digit by digit. If a number comes up with a digit with a value of bigger by one to the compared number, then delete it. Let me show it by using numbers.

Our number is: 123456 Increase the first digit with 1, so the number becomes: 223456. Delete all the 223456s from the file. Increase the second digit by 1, the number becomes: 133456. Delete all 133456s from the file, and so on...

I can do it just as I describe but I need it to be "FAST".

So can anyone help me on this?

Thanks.

Answer 1

First of all, since it is around 1Million you had better perform the algorithm in RAM, not on Disk, that is, first load the contents into an array, then modify the array, then paste the results back into the file.

I would suggest the following algorithm - a straightforward one. Precalculate all the target numbers, in this case 223456, 133456, 124456, 123556, 123466, 123457. Now pass the array and if the number is NOT any of these, write it to another array. Alternatively if it is one of these numbers delete it(recommended if your data structure has O(1) remove)