Учитывая линейный список, есть функция библиотеки в АТС, которая перемешивает список случайным образом, чтобы произвести перестановку него:Есть ли библиотечная функция в ATS для случайной перестановки списка?
fun{a:[email protected]}
list_vt_permute{n:int}(xs: list_vt(a, n)): list_vt(a, n)
Если возможно, я бы предпочел реализацию list_vt_permute, что не вызывает таНос/бесплатно ,
Да, существует такая функция, объявленная в prelude/list_vt.sats, которая основана на функции array_permute, объявленной в prelude/array.sats.
Обратите внимание, что list_vt_permute вызывает list_vt_permute$randint для генерации случайных чисел, и он по существу реализует алгоритм Фишера-Йейта для случайного перетасовки. Функция list_vt_permute - это O (n) -time, и ей необходимо выделить память для временного использования.
Что касается версии list_vt_permute, которая не нуждается в malloc/free, ее можно реализовать как mergesort, взяв O (n * log (n)) - время до завершения.