生成一個字符串的隨機固定長度排列

Question

可以說我的字母表包含X個字母，而我的語言只支持Y字母單詞（Y < X ofcourse）。我需要以隨機順序生成所有可能的單詞。

例如 字母表= A，B，C，d，E，F，G Y = 3

所以話將是： AAA AAB AAC ABA .. BBB CCC .. （以上應該以隨機順序生成）

做這件事的方法很簡單，就是生成單詞然後隨機化列表。我不想這樣做。我想按隨機順序生成單詞。

rondom（n）= letter [x] .random（n-1）將不起作用，因爲那樣你會得到一個以字母[x]開頭的單詞列表，這將使列表不那麼隨機。

任何代碼/僞代碼讚賞。

Answer 1

我想你可以通過基於你有字母字符的隨機陣列（在C＃）做一些很簡單：

 char[] alphabet = {'a', 'b', 'c', 'd'}; 
     int wordLength = 3; 

     Random rand = new Random(); 

     for (int i = 0; i < 5; i++) 
     { 
      char[] word = new char[wordLength]; 
      for (int j = 0; j < wordLength; j++) 
      { 
       word[j] = alphabet[rand.Next(alphabet.Length)]; 
      } 
      Console.WriteLine(new string(word)); 
     } 

顯然，這可能會產生重複，但也許你可以儲存導致hashmap或其他東西來檢查是否需要重複。

Answer 2

所以我認爲你想要的是使用盡可能小的內存產生集合的置換。

首先，它不能使用無記憶。對於你的第一個字符串，你需要一個可以產生任何可能性相同的字符串的函數。說這個函數被稱爲nextString（）。如果再次調用nextString（）而不改變狀態中的任何內容，當然它將再次能夠產生任何字符串。

所以你需要存儲的東西。問題是，你需要存儲什麼，需要多少空間？

可以將字符串看作數字0 - X^Y。 （aaa = 0，aab = 1，aac = 2 ... aba = X ...）所以爲了儘可能高效地存儲單個字符串，您需要lg（X^Y）位。假設X = 16，Y = 2。然後你需要1個字節的存儲來唯一地指定一個字符串。

當然最天真的算法是標記每個字符串，因爲它產生，這需要X^Y位，在我的例子中是256位（32字節）。這就是你說你不想做的事。您可以使用這個問題中討論的shuffle算法：Creating a random ordered list from an ordered list（當您通過shuffle算法生成字符串時，您不需要存儲字符串，但仍需標記它們）。

好吧，現在的問題是，我們可以做得比那更好嗎？我們需要儲存多少，總數？

那麼，在第一次通話時，我們不需要任何存儲空間。在第二次電話會議上，我們需要知道之前製作了哪一個。在最後一次通話中，我們只需要知道哪一個是最後一個。所以最糟糕的情況是當我們半途而廢時。當我們半路過時，已經產生了128個字符串，並且有128個字符串。我們需要知道哪些是留下來生產的。假設這個過程是真正隨機的，任何分裂都是可能的。有（256選擇128）可能性。爲了能夠存儲任何這些數據，我們需要lg（256位選擇128位），根據谷歌計算器是251.67。所以如果你真的很聰明，你可以把信息壓縮成比樸素算法少4位的信息。可能不值得。

如果你只是希望它看起來randomish用很少的存儲，看到了這個問題：Looking for an algorithm to spit out a sequence of numbers in a (pseudo) random order

Answer 3

至於其他的答案已經暗示，有兩種主要的方法：1）跟蹤你已經產生（所提出的解決方案在這個類別中可能永遠不會終止），或者2）跟蹤尚未產生的排列（這意味着排列必須是預先產生的，這在需求中是特別不允許的）。這是另一個解決方案，可以保證終止並且不需要預先生成，但可能不符合您的隨機化要求（在這一點上是模糊的）。

總體概述：生成樹以跟蹤生成的內容或剩餘內容。通過遍歷樹中的隨機鏈接「選擇」新的置換，在生成該置換後修剪樹葉，以防止它再次生成。

如果沒有白板來描述這一點，我希望這個描述足以描述我的意思：創建一個「節點」，其中包含字母表中每個字母的其他節點的鏈接。這可以通過使用通用的字母表到節點的地圖來實現，或者如果您的字母表是固定的，您可以創建特定的參考。該節點代表字母表中可用的字母，可用於生成排列的下一個「生成」。通過訪問根節點開始生成置換，從該節點中的可用字母中選擇一個隨機字母，然後遍歷該引用到下一個節點。每次遍歷時，都會爲排列生成一封信。當到達一片葉子（即完全構建一個置換）時，你會回溯到樹上，看看父節點是否有剩餘的可用排列;如果沒有，父節點可以被修剪。

作爲一個實現細節，節點可以存儲那些不可用於生成的字母集合，或者當前仍然可以生成的一組字母。爲了可能減少存儲需求，您還可以允許節點存儲或並附上一個標誌，指示它正在做什麼，以便當節點允許一半以上的字母表存儲迄今爲止產生的字母並切換到使用字母只有少於一半的字母可用時仍然存在。

使用這樣的樹結構限制了可以生成的內容，而無需預先生成所有組合，因爲您不需要預先構建整個樹（它可以構造爲生成排列），而且您保證完成，因爲清除節點（也就是說，你只是遍歷節點的鏈接，當這是一個允許的組合產生非產生的排列）。

然而，我認爲該技術的隨機化有點奇怪，我不認爲每個組合在任何給定時間都可能產生的可能性相同，儘管我沒有真正想過這一點。也可能值得注意的是，即使完整樹不一定是預先生成的，所涉及的開銷可能足以使您預先生成所有排列可能更好。