To Adak,
I must clarify the problem. When I mean consecutive numbers, I am not
saying the values are consecutive, but the positions of the numbers.
So in sequence of number {2, 4, 5, 7, 1, 23, 41, 12}, {5, 7, 1} is a
segment of consecutive numbers. But {2, 5, 7} is not because 4 is
missed between 2 and 5.
So what you said: "...Scan the numbers, putting all sequences with
consecutive numbers, in another array..." is not applicable here.
As you curious about, this is a subproblem of a larger research
problem. In the research project, we want to discover regularly
occurring patterns. A such pattern contains K identical blocks. These
K blocks happen with a similar interval in the long signal sequence.
So far I do not have any good solution whose worst case is better than
O(L^2), L is the longest segment satisfying the user defined values. I
scan the sequence of numbers, and keep min and max values until I can
not go any further. This means that the number stops me (denoted as T)
must be smaller than min or bigger than max. Assuming it is bigger
than max and (T - min) is larger than d (user defined value, see
original question). We know that the current segment can not be
extended further (because of T) and we should start from the number
next to min. For any segment which can not be extended further, if its
length is greater than f (user defined value, see original question),
it is output.
Obviously, in worse case, the above solution works in O(L^2). Such an
example is: find all segments with f >= 5, d <= 4 from the sequence:
1,2,3,4,5,6,7,8,9
The above solution works as:
1. initial segment {1}, extend it to {1,2} with the min and max marked
for the newly extended segment. Until {1,2,3,4,5} with min=1, max=5.
2. This segment is stopped by 6 (since 6-1>4). Start from the number
next to min (which is 2). Scan through 6. New segment is {2,3,4,5,6}.
Extend it to 7 but failed.
3. Scan from 3 to 7. New segment {3,4,5,6,7}. Stopped extending it at
8.
4. Scan through 4 to 8 and so on.
I wonder whether there are any better solution to this?
regards
Sticker
On Sep 5, 12:38 am, adak <[EMAIL PROTECTED]> wrote:
> Well, now you've gone and given me Sicker shock! :)
>
> Dilly of a problem, I must say!!
>
> I can't offer you a possible solution, but I'm curious what algorithms
> you've tried for this problem, and what was the resulting
> performance?
>
> I was thinking, something like:
>
> Scan the numbers, putting all sequences with consecutive numbers, in
> another array. (or assigning pointers to the start and end of each).
> At the same time, you're also accumulating the various sub-totals
> you'll need for later calculations. 2 flags would denote which
> consecutive
> sequences met the requirements of being larger than d, etc.
>
> A file for the data and processing it in chunks that will fit into
> arrays on your system's memory, might be needed.
>
> I hope you'll let us know what you discover. Is this part of an
> assignment or programming problem competition?
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
