7/6/2023 0 Comments Python permute list randomly![]() Maybe use a larger array? But then traversing it will take longer. the Fisher-Yates shuffle) is an algorithm for randomly shuffling the elements of an array. I've thought about non-Haskelley ways of doing it with arrays, but it seems hard to efficiently deal with the "holes" in the arrays if you use an approach that removes elements, and hard to efficiently find the nearest hole if you use an approach that inserts elements. Building the tree could take O(n) if you use the equivalent of, but walking the tree and removing all the elements would still take O(n∙log(n)). ![]() Is this problem studied in theoretical CS? It takes O(n∙log(n)) to sort a list, so does it necessarily take as long to unsort the list? Because that would be the runtime complexity of unsorting it with a tree. One possible way would be to produce a 2-3 tree, and then randomly walk down the tree and remove nodes, but writing your own 2-3 tree for this purpose is a lot of work. It is unclear to me how to do this simply in Haskell. I'm asking this as a purely intellectual exercise, but a while ago, I did really need to produce a random permutation of a list.
0 Comments
Leave a Reply. |