真正大排列表

我的問題不是語言特定的。我遇到了處理排列循環的問題。我試圖編寫一些代碼來顯示26^x的所有值，其中x是字符串的長度。沒有輸入的字符串會被提供，所以如果x=1，它會通過ž顯示一個，如果x=2 ITLL顯示AA通過ZZ。 az被認爲不同於za。真正大排列表

更具體地說，我想運行這個更長的字符串，長度超過100個字符，試圖查看給定長度的字符串包含多少個字符而不是隨機字母。

來源

2012-04-13 Rickie Marsh

時間複雜度和單詞數量是n !, 100個字符是9 * 10^157。任何算法都需要很長時間才能讓這些單詞更少地處理它們。 – 2012-04-13 05:07:51

（根據我的理解）您可以計算您的程序生成的長度的單詞數量。使用字典庫來計算給定長度的字數。現在，您可以看到隨機字母的數量。 – 2012-04-13 06:44:48

@JesusRamos你可以擲出一枚公平的硬幣1000001次，模擬它將需要2^1000001步，但幾乎沒有時間預測'頭'贏了還是輸了！ – ElKamina 2012-04-13 06:52:30

根據對該問題的評論，嘗試枚舉所有可能的100個字符的字符串是不切實際的。

我會建議生成給定長度的隨機字符串的替代策略，而不是以結構化方式枚舉。例如：

count = 0 
for i from 0 to simulation_length: 
    random_string = '' 
    for j from 0 to string_length: 
     random_string += random_char() 
    // containsWord(string) checks if the random string contains a word 
    // this is tricky in and of itself 
    if (containsWord(random_string)) count++ 
...

只要simulation_length足夠，隨機採樣就會給出整個空間行爲的表示。

來源

2012-04-13 05:15:53 mfrankli

您可以通過將總詞數對於每個長度'n'和除以'n！'，這將是長度爲'n'的字母串的部分，它們是單詞。我認爲OP在詢問是否將單詞作爲一個子集，但這很難。 – Dougal 2012-04-13 05:18:06

是的，這也是我的解釋（因此我的答案沒有多大意義，否則），但代碼並沒有真正反映出來。正在編輯... – mfrankli 2012-04-13 05:20:22

26^x，其中x是一個字符串的長度...我想長

你應該忘掉它的長字符串運行此，超過100個字符。

讓我們來看看事物。英語字母表中有26個字母，因此其中有100個字符的字符串總數是...

3142930641582938830174357788501626427282669988762475256374173175398995908420104023465432599069702289330964075081611719197835869803511992549376

這是十進制數。每毫秒1個字符串的速度將花費9.9 * 10^130年來全部打印。這比宇宙長7.3×10^120倍。

獲取單詞列表或將字典加載到內存中，然後使用它。

來源

2012-04-13 05:17:51 SigTerm

我明白了這一點。我計劃隨機使用前兩個字符進行手動檢查。如果不可能開始一個詞，它會放棄這條路。我可能說我的問題錯了，因爲它更多的是從兩個字符開始，檢查一個單詞是否可能，如果是，則添加另一個字符並重復，直到任何單詞不可能或字符串長度已達到。如果不可能，移動到該位置的下一個字母。 – 2012-04-13 06:31:01

通過爲前兩個字符設置一些簡單的規則，可以消除大量的搜索/處理。如果q是第一個，那麼第二個只能是元音。其他一些字母也是如此。 26^2可能的兩個字母組合，q例如只有5個有效組合，它是第一個字母。雖然設置許多規則仍然沒有樂趣，但它確實消除了很多問題。此外，由於我正在考慮在給定位置使用特定單詞的字符串，因此可以在單詞前後分爲兩部分。 – 2012-04-16 10:28:58

我們現在想看到的是：有多少個字符串的大小爲50,51,52 ......可以從字典中用以下單詞構建：「2：183,3：815,4：3181,5： 6151,6：9317,7：11962,8：11979,9：10400,10：8065，......「從{2..20}中的n代替你的值;做echo -ne「$ n \ t」; egrep -v「。*」s「/ usr/share/dict/american-english | egrep -c「^。{」$ n「} $」;完成' – 2012-05-09 19:54:38

這取決於你對'單詞'的定義。如果'a'是一個單詞，那麼獲得以100個字符序列獲得單詞的概率的下限是非常容易的（大致爲1 1/e^4）。同樣，你可以考慮2個字母的單詞和3個字母的單詞，並提高概率。在4或5個字母之後，這個概率變得非常準確，因爲有幾個更長的單詞，並且它們隨機發生的情況非常罕見。

來源

2012-04-13 06:42:25 ElKamina

給定字符串長度中的多個單詞。如果用戶輸入8，則可以返回「itisadog」或「wesaidno」。這樣看，有一本字典，並尋找所有的話加起來到給定的長度似乎更好 – 2012-04-13 10:23:44

@RickieMarsh：但你不指望他們有道理？那麼'nosaidwe'和'nonoweno'會適合嗎？ – 2012-05-09 16:23:59

真正大排列表

回答

相關問題