Уникумы колец чисел постоянной длины - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Уникумы колец чисел постоянной длины (http://forum.oszone.net/showthread.php?t=136019)

Уникумы колец чисел постоянной длины

Здравствуйте, форум

Задача: вызвать в Pascal входной файл simv.txt таблицы строк одинаковой длины, "закольцевать" строки и оставить единичных представителей колец чисел, они же строки постоянных длин.
Объясняю: Если нанизать на кольцо нумерованные шары (ожерелье), невозможно будет
сказать, какой из них первый. Разве что договориться. В производимой программой
вывода последовательностей постоянной длины строк массе текста среди прочих строк будут попадаться, к примеру, такие:
...
1 3 1 1 5 5 1
...
3 1 1 5 5 1 1
...
1 1 5 5 1 1 3
...
1 5 5 1 1 3 1
...
5 5 1 1 3 1 1
...
5 1 1 3 1 1 5
...
1 1 3 1 1 5 5
...
Но ведь это кольцо. А у кольца начала нет, и... Задача: где найти
программу с опцией: напечатать одного представителя кольца, а всех
остальных удалить. В первой строке самый первый символ
переставляется в конец строки, вся строка сдвигается влево и
сравнивается со всеми строками всей таблицы. При выявлении в
толще таблицы двойника, найденный второй дубликат убивается.
Программа возвращается к первой строке, теперь уже второй
символ переносится в конец строки, сдвиг и все по новой. И так по
очереди с третьим, четвертым и т. д. символами. Повторить столько
раз сколько имеется столбцов минус единица. Можно начать и с конца
строки. Сама таблица тоже сократится во столько раз, сколько имеется
столбцов. И будет программа вывода последовательностей с
представлением единичных представителей колец чисел. Так приблизительно
представляется. Здесь непонятно, как перейти к следующей строке? А строк тысячи. Не могли бы Вы расписать шаги для обработки нижеследующего поимера:

1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1 3 1
1 1 1 1 1 1 2 1 2
1 1 1 1 1 1 2 2 1
1 1 1 1 1 1 3 1 1
1 1 1 1 1 2 1 1 2
1 1 1 1 1 2 1 2 1
1 1 1 1 1 2 2 1 1
1 1 1 1 1 3 1 1 1
1 1 1 1 2 1 1 1 2
1 1 1 1 2 1 1 2 1
1 1 1 1 2 1 2 1 1
1 1 1 1 2 2 1 1 1
1 1 1 1 3 1 1 1 1
1 1 1 2 1 1 1 1 2
1 1 1 2 1 1 1 2 1
1 1 1 2 1 1 2 1 1
1 1 1 2 1 2 1 1 1
1 1 1 2 2 1 1 1 1
1 1 1 3 1 1 1 1 1
1 1 2 1 1 1 1 1 2
1 1 2 1 1 1 1 2 1
1 1 2 1 1 1 2 1 1
1 1 2 1 1 2 1 1 1
1 1 2 1 2 1 1 1 1
1 1 2 2 1 1 1 1 1
1 1 3 1 1 1 1 1 1
1 2 1 1 1 1 1 1 2
1 2 1 1 1 1 1 2 1
1 2 1 1 1 1 2 1 1
1 2 1 1 1 2 1 1 1
1 2 1 1 2 1 1 1 1
1 2 1 2 1 1 1 1 1
1 2 2 1 1 1 1 1 1
1 3 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 2
2 1 1 1 1 1 1 2 1
2 1 1 1 1 1 2 1 1
2 1 1 1 1 2 1 1 1
2 1 1 1 2 1 1 1 1
2 1 1 2 1 1 1 1 1
2 1 2 1 1 1 1 1 1
2 2 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1 1

?
Спасибо

такое ощущение, что читаю машинный перевод - какое-то бессвязное нагромождение слов

картинка красивая из циферок получилась
burany, а мона твои намётки на решение, а то вооще не понятно, о чём речь

pva, наметок почти и нет:

var f : text;
s : char;
begin
assign(f, 'C:\c20c.txt');
reset(f);
while not Eof(f) do
begin
read(f, s);
write(s);
end;
close(f);
end.

а также:

{function AnsiCompareStr(s2, s0 :string) : integer;}
var
s : string[18];
s1 : string[2];
begin
s := ' 1 12 23 24 25 36';
s1:= copy(s,17,2);
delete(s,17,2);
insert(s1,s,1);
writeln(s);
{AnsiCompareStr:=(s2, s0);}
end.

Как все это связать? Задача, ведь, подробно расписана.

burany, до меня трудно доходит. Нужно найти период повторения строки при циклическом сдвиге влево?
Всё, дошло. В общем я так понимаю, что это задача распознавания образов. Придётся делать перебор (сравнение всех между собой). Вариант 1:

Код:

function cyclic_equal(string a; string b): boolean;

var i: integer;

begin

  i:=1;

  result := false;

  while (not result) and (1<=length(a)) do begin

    result := b = copy(a, i, n-i) + copy(a, 1, i);

    inc(i);

  end

end;

...

var input_strings : array of string;

...

for i:=low(input_strings) to high(input_strings) do begin

  for j:=i+1 to high(input_strings) do begin

    if cyclic_equal(input_strings[i], input_strings[j]) then writeln('удалить вариант ', input_strings[i]);

  end

end

Второй вариант (извращенский), когда ооочень много строчек, а их длина есть степень двойки.
1. для каждой строчки делаем быстрое преобразование фурье, либо быстрое преобразование косинусов (требует длину - степень двойки, при циклическом сдвиге меняется только фаза фурье)
2. составляем строчки из амплитуд частот
3. сортируем список по полученным строчкам амплитуд (посимвольно) быстрой сортировкой
4. сравниваем между собой только внутри подмассивов с посимвольно одинаковыми амплитудами (на случай когда 2 разных сигнала имеют одинаковый частотно-амплитудный состав)

По поводу непонятки, последнее слово строки ставится в
начало строки, вся строка сдвигается к хвосту, пробелы сохраняются
(важно!). Получаются две одинаковые строки, или более:

3 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1 1
- - -

Надо оставить одну.

Pva, ты прогонял свои функции на циферках из красивой
картинки? А то что-то у меня не сразу.

Попутно вопрос: можно ли превратить строку в динамический
список, а конкретно, в кольцо?

Цитата:

Цитата burany

Pva, ты прогонял свои функции на циферках »

Нет конечно, я только идею передал. Стопудово в коде есть простые глюки, но ты их выловишь ;)

Цитата:

Цитата burany

строку в динамический
список »

да, вместо `string` пиши `array of TЧтонибудь` и переделай функцию cyclic_equal

Всем большое спасибо