bogoソートを最適化するにはどうすればよいですか？

Question

私はbogoソートを作成しましたが、最適化します。 1つの文字に分割された文字列をランダムにシャッフルします。しかし、文字をシャッフルすると、ランダム置換を複数回繰り返すことができます。たとえば、単語が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

これを実装することは可能でしょうか？

はい、もちろんです。他の人は既にその問題の解決策を考え出していました。 shuffleの代わりにHeap's AlgorithmまたはSteinhaus-Johnson-Trotter Algorithmを使用できます。どちらのアルゴリズムもすべて可能です。N！現時点での順列。N！ステップ。

これにより、隠されたバグも修正されます。でも小さいlen（x）は、X の順列の総数はすぐに最も乱数ジェネレータ の期間より大きく成長することができます

注：​​random.shuffle(x)のから。これは、の長いシーケンスの順列は が決して生成されないことを意味します。例えば、長さ2080のシーケンスは、メルセヌント・ツイスター・ランダム 番号ジェネレータの期間内に収まる最大の です。

バグは、おそらくあなたのユースケースには発生しませんが、それは（Y2K問題を覚えて）それにもかかわらず、それを修正するために良いことです。

Answer 2

具体的には、itertoolsモジュールがあり、itertools.permutationsはすべての可能な置換のイテレータを生成します。また、そのような関数を誰がどこに実装できるかを見ることができます。ちょうど楽しみのため

：私はので、私はあなたのためにこれを実装することはできませんのpythonを知らない

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.")