实施bogos的问题

Question

出于某种原因，我决定用python实现万能的bogosort，并编写了以下代码：

import numpy as np

def checkSorted(x):
  if x == sorted(x[:]):
    return True
  else:
    return False

def bogosort(x):
  np.random.shuffle(x)
  if checkSorted(x):
    return
  else:
    bogosort(x)

arr = [1,3,2]
bogosort(arr)
print(arr)

当数组大小超过4时，我会得到以下错误：

RecursionError: maximum recursion depth exceeded while calling a Pythonobject

哎呀！我找到了解决方法，它是：

import sys
sys.setrecursionlimit(50000)

如果数组大小为8，这应该很好，因为8！是40320，但这次我遇到了分割错误

repl process died unexpectedly: signal: segmentation fault (core dumped)

哎呀！我想这一次它的内存不足，崩溃了。有没有办法提高允许的内存使用率来防止这种情况

我真的希望这个算法能够在至少10个数组大小的情况下工作，这样我就可以画一个图表，将它与其他算法进行比较，因为像quicksort这样的东西甚至不能在输入小于10的情况下计时

Answer 1

由于随着数组大小的增加，bogosort可能需要非常非常长的时间才能运行，因此最好使用迭代而不是递归。这是因为较大的数组很容易超过递归深度

在这里，我编辑了您的代码以使用循环。我还使您的一些代码更加简洁

import random

def checkSorted(x):
    # A more concise way is to just return the comparison,
    # which will evaluate to either True or False.
    return x == sorted(x)

def bogosort(x):
    # Instead of using recursion, you could use iteration.
    # List x will continue to be shuffled until it is sorted.
    while not checkSorted(x):
        random.shuffle(x)
    # Once x is sorted, return it.
    return x

# Here, I just initialized arr as a list of integers from 0 to 5, excluding 5
arr = list(range(5))
# To test bogosort, let's shuffle the list beforehand
random.shuffle(arr)
# Run bogosort, then print the sorted array
bogosort(arr)
print(arr)

我还使用了Python的内置random模块。不过，如果需要，您可以自由地使用numpy