Как искать нарушения в очередности последовательности чисел?
Последовательность чисел такая, что они принимают значения от 0 до 15, а потом снова с нуля.

Пример последовательности: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 12, 2, 13, 14, 15, 0, 1, 2.

Видно, что в последовательности числа 1 и 2 лишнии. Как идентифицировать подобное поведение и подсчитать ошибки в очередности? Буду рад выслушать идеи, или посмотреть готовые алгоритмы 

Базовая последовательность конечна и все ее элементы принимают значения от 0 до 15 строго инкрементируя друг за другом ровно на единицу. "Лишние" элементы тоже принимают значения от 0 до 15, которые случайны.

Это сообщение отредактировал(а) valzy - 8.4.2008, 09:55

начинать с индекса i=0 , перехоим к i=1 .проверяем a[i]?=a[i-1] , если да идём дальше, если нет , начинаем выбрасывать числа из последовательности пока:  a[i]!=a[i-1]

начать стоит со списка возможных искажений
на примере - вставка какого-то числа
какие-то ещё возможны? (замена, удаление, ...)

Это сообщение отредактировал(а) maxim1000 - 6.4.2008, 00:23

Известен ли предел "ошибки"? Есть ли гарантия непрерывности базовой последовательности?

Базовая последовательность конечна и все ее элементы принимают значения от 0 до 15 строго инкрементируя друг за другом ровно на единицу. "Лишние" элементы тоже принимают значения от 0 до 15, которые случайны.

В таком случае простейший алгоритм - для каждого значения искать следующее. Если оно и в ряду по положению следующее - в данной точке неправильности нет.

Но это полдела. Все найденные неправильности следует также проверить на принадлежность основной последовательности.

Вот исходник на С++ этого алгоритма


Так...до кучи ))

Всем спасибо! Буду разбираться.
Еще возможен такой случай, что в последовательности группа элементов распологается впереди относительно другой группы элементов, которая должная была быть первой. Т.е:
3 4 5 6 7 8 9 0 1 2 10 11 12 13 14 15
Как здесь можно отловить нарушение в очередности? Сам даже и не знаю... 
P.S. А вообще этот алгоритм чем-то должен быть похожим на тот, в котором происходит поиск нарушений в очередности пакетов MPEG-2 Transport Stream и их потерь. Кто знает, тот поймет. Вот его бы не мешало посмотреть, т.к. в нем появилась острая необходимость.

Это сообщение отредактировал(а) valzy - 7.4.2008, 21:20

а что в этом случае надо сделать ?  выбросить 0 1 2 или  поставить их на место перед 3 4 ...

Подсчитать количество таких нарушений. Переставлять нет нужды.

ну так, все такие нарушения будут выявляться тем алгоритмом, что я описал в первом своём посте.
может непонятно написал...

Я об этом уже говорил... 


Интересно, чем определено, что неправильность - это именно "0 1 2", а не всё остальное? Для меня это более чем неочевидно. Пока, во всяком случае... я уж не говорю о вариантах типа:
0 1 0 2 1 2 3 3 4 5 4 5 6 7 8 6 7 9 10 8 9 10 11 12 11 13 14 12 13 14 15 15
Ну-ка, покажите тут основную последовательность и "неправильности"   

значит в таком случае выбрать начальную (самую длинную? ) правильную последовательность (возможно где то в средине она будет) и от неё отталкиваться.

Утренние мысли:
1) от неправильности типа "повторения" можно избавиться путем слияния(выражаюсь некорректно) Пример. 15 15 15 15 15 -> 15 И где-нибудь отметим, что неправильность типа "повторение" исправлена
2) неправильность типа "пик или впадина". Идея графическая. Идти по графику и отыскивать в нем эти неправильности(некорректно выражаюсь). Так как мы ликвидировали неправильности типа "повторение", то можем смело делать так: если обнаруживаем, что слудующая точка после текущей рассматриваемой отличается от нее более чем на 1, то её принимаем во внимание за начало неправильности(вдруг неправильность вида 10 11 0 1 0 12). Идем далее по списку точек, пока не найдем ту, которая на 1 больше чем точка, с которой начался весь сыр бор.
Пример.


Ой ой. Начальную точку тоже как-нибудь проверяйте. Ноль или единица- вам решать.

Вот последовательность от Акины, приведеная в правильный вид. Красным - неправильности типа впадин, синим- типа повторений. Повторения превращаются в 1 число, как сказано в начале поста. Начало с 0.
0 1 0 2 1 2 3 3 4 5 4 5 6 7 8 6 7 9 10 8 9 10 11 12 11 13 14 12 13 14 15 15

0 1 0 2 1 2 3 3 4 5 4 5 6 7 8 6 7 9 10 8 9 10 11 12 11 13 14 12 13 14 15 15

Добавлено через 6 минут и 23 секунды
Прошу найти контр-пример, чтобы можно было думать дальше 

Добавлено через 7 минут и 59 секунд




Это сообщение отредактировал(а) SoWa - 8.4.2008, 06:22

Я не зря привел пример, где перемешаны две абсолютно одинаковые базовые последовательности.


Неправильность типа "повторение" не оговорена. Единственный оговоренный тип неправильности - это когда