Хоть и не пятница, но задачка

← →
Alkid (2008-12-11 14:56) [0]

Если вам сейчас особенно нечем заняться :)

Дано: есть X символов. Очевидно, что из них можно получить X^K различных строк символов, если длина строки равна K.

Вопрос: сколько из них можно получить различных строк, если считать равными любые 2 строки, которые можно получить друг из друга путём циклического сдвига. Т.е. строки вида "ABCD", "BCDA", "CDAB" и "DABC" считать равными.

Интересует процесс вывода формулы на предмет совпадения (или не совпадения) стиля мышления.

← →
БарЛог © (2008-12-11 15:22) [1]

Ну тут, имхо, мыслить будешь по-любому одинаково:
из-за сдвига имеем вместо К-строчек одну (делим на К), предварительно вычитаем число строк, состоящих из одинаковых символов (их число - Х).
прибавляем Х.

так?

← →
Правильный$Вася (2008-12-11 15:26) [2]

равные только при цикличном сдвиге? т.е. "BACD" приведенным не равна?

← →
Bless © (2008-12-11 15:30) [3]

> БарЛог © (11.12.08 15:22) [1]
>
> Ну тут, имхо, мыслить будешь по-любому одинаково:
> из-за сдвига имеем вместо К-строчек одну (делим на К), предварительно
> вычитаем число строк, состоящих из одинаковых символов (их
> число - Х).
> прибавляем Х.
>
> так?

Неа :)
Не учел никак строки вида XYXY.

← →
Bless © (2008-12-11 15:32) [4]

К тому же не исключено, что кроме "xyxy" и "xxxx" есть еще какие-нибудь "особые случаи", не знаю...

← →
БарЛог © (2008-12-11 15:34) [5]

> Не учел никак строки вида XYXY.
омг! еще же XYZ и т.п.

← →
БарЛог © (2008-12-11 15:36) [6]

А, ну тада делим на 1*2*3*4*5*...*X

← →
Bless © (2008-12-11 15:39) [7]

> Alkid (11.12.08 14:56)

Вопрос "сколько из них можно получить различных строк"
следует читать как "сколько из них можно получить различных строк длины К"?

← →
MBo © (2008-12-11 16:19) [8]

Формула, однако, вовсе не тривиальная...
Например, для бинарных строк (алфавит {0,1}) только подсчет по формуле займет порядка N*logN.

← →
Alkid (2008-12-11 18:03) [9]

Сорри, отвлёкся.

> БарЛог © (11.12.08 15:22) [1]

Нет, не правильно. Точнее, это частный случай формулы для всех простых K.

> Правильный$Вася (11.12.08 15:26) [2]
>
> равные только при цикличном сдвиге? т.е. "BACD" приведенным
> не равна?

Да, только при циклическом сдвиге.

> Bless © (11.12.08 15:39) [7]

Да, все строки имеют длину K.

> MBo © (11.12.08 16:19) [8]

Формула не тривиальная, согласен. Но речь идёт не о перечислении всех возможных вариантов, а о подсчёте их количества. Количество всех бинарных, позиционно различающихся строк равен длиной K равен X^K и вычисление этого выражения никак не требует K*log(K) дейсвий.

← →
БарЛог © (2008-12-11 18:35) [10]

(X^K)/(K*K!) + X ?

K! берется из-за
Bless © (11.12.08 15:32) [4]
Из-за таких строк:
XYXYXY...
XYZXYZ...
....

что еще не учитывается?

← →
Alkid (2008-12-11 18:41) [11]

> БарЛог © (11.12.08 18:35) [10]

Мысли верны, но формула другая. Хотя вообще, не исключаю, что моя формула может быть приведена к твоей и обратно. Как выводил можешь объяснить?

← →
Alkid (2008-12-11 18:45) [12]

> БарЛог © (11.12.08 18:35) [10]
> что еще не учитывается?

Обрати внимание, что повторяющаяся последовательность должна укладываться в строку целое число раз. Т.е. для строки длиной 4 будет два варианта:
XXXX и XYXY. А для строки длиной 5 будет только 1 - XXXXX.

← →
БарЛог © (2008-12-11 19:21) [13]

вышли, пожалуйста, ответ, если не хочешь публиковать.
yashik2000sobMail.ru
Чтоб не гадать.

← →
Alkid (2008-12-11 21:02) [14]

> БарЛог © (11.12.08 19:21) [13]

С выводом или без вывода?

Ссылка по теме
http://www.omsu.omskreg.ru/vestnik/articles/y1998-i2/a021/article.html
Также можно почитать об этой задаче в учебнике алгебры Кострикина, если у кого завалялась эта книга.

← →
Alkid (2008-12-11 22:07) [16]

Alkid (11.12.08 22:07) [16]
Скорее всего не испортил. Извиняюсь, в статье рассматривается другая задача.

← →
Alkid (2008-12-12 00:50) [18]

Да. В этой задаче отражение не делает строки равными

Вот еще одна ссылка - понятная толковая статья
http://alexei.stepanov.spb.ru/students/algebra3/Bernside.pdf

>Количество всех бинарных, позиционно различающихся строк равен длиной K равен X^K и вычисление этого выражения никак не требует K*log(K) дейсвий.

Этого выражения - не требует, но известная мне формула для сдвигово-эквивалентных строк - увы, требует.

Хоть и не пятница, но задачка Найти похожие ветки