Как я могу оптимизировать сортировку bogo?

Question

Я создал тип bogo, но хочу его оптимизировать. Он случайным образом перемещает строку, которая была разделена на отдельные символы. Однако, когда он перемещает символы, он может повторять случайную перестановку более одного раза. Например, если слово cat, оно может попробовать «tac» или «act», но затем оно может попробовать «tac» снова. Я хочу закодировать его, чтобы один раз попробовать только одну перестановку, но я не уверен, как это сделать. Это мой код в python. Можно ли это реализовать?

import random 

i=0 
valid = False 
while not(valid): 
    word = input("Enter word to be mixed > ") 
    if len(word) <= 1: 
     ("not valid!") 
    else: 
     valid = True 

wordlist = list(word) 

resorted = False 
while not (resorted): 
    random.shuffle(wordlist) 
    i += 1 
    print ("attempts", i) 
    print (wordlist) 
    if list(word) == wordlist:   
     print ("Sorted!") 
     break 

Answer 1

Можно ли осуществить это?

Да, конечно. Другие люди уже придумали решение этой проблемы. Вы можете использовать Heap's Algorithm или Steinhaus-Johnson-Trotter Algorithm вместо shuffle. Оба алгоритма генерируют все возможные N! перестановки в exatcly N! шагов.

Это также устранит скрытую ошибку. Из documentation из random.shuffle(x):

Обратите внимание, что даже при малых Len (х), то общее число перестановок х может быстро расти больше, чем период большинства случайных чисел генераторов. Это означает, что большинство перестановок длинной последовательности может никогда не генерироваться. Например, последовательность длиной 2080 является наибольшей величиной , которая может вписываться в период произвольного генератора чисел Mersenne Twister.

Ошибка, вероятно, не произойдет в вашем прецеденте, но все же полезно исправить ее (помните о проблеме y2k).

Answer 2

Для Python специально существует модуль itertools, а itertools.permutations генерирует итератор всех возможных перестановок. Вы также можете увидеть, какая такая функция может быть реализована там.

Просто для удовольствия: Можно даже просто имитировать Бого-то со следующим фрагментом:

import itertools 
import random 

word = input("Enter the word to be mixed >") 
perms = list(itertools.permutations(word)) 

# This is the random part: 
random.shuffle(perms) 

print("Needed", perms.index(tuple(word)), "attempts.")