Задача 338: За любителите на аритметиката и информатиката (накуп)

[Bibi]

Нали търсим алгоритъм? Значи езиците нямат значение. Или греша?

А всъщност имам въпрос: какво да разбираме под "подреждане по случаен начин"?
Ако трябва да е пълна липса на закономерност в подредбата, за сега не мога да си представя как това би могло да се постигне с алгоритъм. По принцип.
А ако става дума за по-слабото - закономерност, която не може да бъде видяна с просто око, тогава е друго. Макар че още нямам никаква идея, освен изтърканите манипулации с часовника.

[dedis]

Езиците нямат значение. Споменах за интерпретатор заради отчетливо бавната работа.
Имах предвид проста работа - с random. Това за часовника не го знам, може би е оптимално?

[Bibi]

Т.е. ти казваш, че може да се ползва вградения random() на някой език и с негова помощ, така ли?
Аз помислих нещо по-дълбоко. Че ще пишем как работи самия random().
И навремето в Паскал, мисля, че работеше, взимайки показанията на часовника. За да дава всеки път различен резултат, трябва да започва с нещо, което се мени.

Всъщност ние искаме ли всяко стартиране на алгоритъма да ни дава различно подреждане?

[dedis]

Т.е. ти казваш, че може да се ползва вградения random() на някой език и с негова помощ, така ли?
Аз помислих нещо по-дълбоко. Че ще пишем как работи самия random().
И навремето в Паскал, мисля, че работеше, взимайки показанията на часовника. За да дава всеки път различен резултат, трябва да започва с нещо, което се мени.

Всъщност ние искаме ли всяко стартиране на алгоритъма да ни дава различно подреждане?

Не, не искаме, по-точно - няма значение. Но може да инициализира random-а с днешната дата (така съм направил програмка за числата на тотото). Може да се добави и часа
Всъщност търсим максимална бързина на алгоритъма, като приемаме, че генерирането на случайно цяло число в даден диапазон не е проблем.
Един възможен алгоритъм е, например:
- генерира се число от 1 до N,
- записва се на първо място,
- генерира се ново,
- проверява се дали не е вече излязло,
- ако не е - записва се на следващото място и т.н. до изчерпване на N-те числа.
Този алгоритъм обаче е много бавен за големи N. Примерно над 10^5.

[Bibi]

Сега ми се спи, но едно такова и от мен:
- записваме ги последователно
- избираме две произволни и им разменяме местата -> това в цикъл с някаква постоянна или пък с random дължина

[dedis]

Не ми харесва (в смисъла на условието).
Както в примерния алгоритъм, който дадох, така и при твоя, броят на необходимите цикли за включване с голяма вероятност на всички числа (N на брой) в процеса нараства много стръмно с нарастването на N.
Примерно, при N=10^6, направи сметка колко цикъла са необходими за да се избере дадено число К(N) с доверителна вероятност 99% примерно. За да бъдат "омешани" всичките. Дори бих добавил подусловие - всичките членове да вземат участие. Не че не може случайно някои да си останат на първоначалните места, но това да е минало през процеса, да е наистина случайно.

[Bibi]

Tо не че на мен ми харесваше.

А така:
Взимаме някакво число, взаимно просто с N. Може да вземем някое просто число P за по-лесно.
Започваме от random начало.
Следващите да са предното плюс P по модул N.
Така с N стъпки ще ги разбъркаме.

[dedis]

Щом казваш...