從多個字符生成排列

Question

我正在研究預測性文本解決方案，並根據特定字符串的輸入從Trie中檢索所有單詞，即「at」將提供所有以「at」作爲前綴。我現在面臨的問題是，我們也應該按下移動電話上的這兩個按鈕，即按鈕2和按鈕8，以返回所有其他可能性，這也可以使用「au，av，bt，bu ，bv，ct，cu，cv「（其中大多數不會有任何實際的字詞）

任何人都可以提出一個解決方案，我會如何去做這個計算不同的排列？ （目前，我提示用戶輸入前綴（不使用GUI現在）

Answer 1

歡迎像遞歸性和組合爆炸:)

由於組合爆炸的概念，你必須是「智能「關於它：如果用戶想要輸入一個合法的20個字母的單詞，那麼解決方案」掛「試圖愚蠢地成千上萬的可能性是不可接受的。

因此，只有當trie至少有一個條目用於前綴時，您才應該進行遞歸處理。

以下是一種生成所有前綴的方法，只有匹配時才進行遞歸。

在這個例子中，我僞造了一個總是說有條目的樹。我在五分鐘內做到了這一點，所以它肯定可以美化/簡化。

這樣的解決方案的優點是，如果用戶按下一個，兩個，三個，四個或'n'鍵，而無需更改您的代碼，它的工作原理。

請注意，您可能不想添加全部當字符太多時，以'x'字母開始的單詞。您需要找到最適合您需求的策略（等待更多按鍵來減少候選人或添加候選人最常見的匹配項等）。

private void append(final String s, final char[][] chars, final Set<String> candidates) { 
     if (s.length() >= 2 && doesTrieContainAnyWordStartingWith(s)) { 
      candidates.add(s + "..."); // TODO: here add all words starting with 's' instead of adding 's' 
     } 
     if (doesTrieContainAnyWordStartingWith(s) && chars.length > 0) { 
      final char[][] next = new char[chars.length-1][]; 
      for (int i = 1; i < chars.length; i++) { 
       next[i-1] = chars[i]; 
      } 
      // our three recursive calls, one for each possible letter 
      // (you'll want to adapt for a 'real' keyboard, where some keys may only correspond to two letters) 
      append(s + chars[0][0], next, candidates); 
      append(s + chars[0][1], next, candidates); 
      append(s + chars[0][2], next, candidates); 
     } else { 
      // we do nothing, it's our recursive termination condition and 
      // we are sure to hit it seen that we're decreasing our 'chars' 
      // length at every pass 
     } 
    } 

    private boolean doesTrieContainAnyWordStartingWith(final String s) { 
     // You obviously have to change this 
     return true; 
    } 

請注意遞歸調用（僅當存在匹配的前綴時）。

這裏是你如何可以把它稱爲：我僞造用戶按壓「1」，則「2」，然後「3」（我在字符炭[] []數組我創建僞造此）：

public void testFindWords() { 
     // Imagine the user pressed 1 then 2 then 3 
     final char[][] chars = { 
       {'a','b','c'}, 
       {'d','e','f'}, 
       {'g','h','i'}, 
     }; 
     final Set<String> set = new HashSet<String>(); 
     append("", chars, set); // We enter our recursive method 
     for (final String s : set) { 
      System.out.println("" + s); 
     } 
     System.out.println("Set size: " + set.size()); 
} 

該示例將創建一個包含36個匹配的集合，因爲我「僞造」每個前綴都是合法的，並且每個前綴都會導致恰好一個單詞（並且，只有當它由至少兩個字母組成時才添加「單詞」 ）。因此3 * 3 * 3 + 3 * 3，這給出了36.

您可以嘗試一下代碼，它完全正常工作，但您必須對其進行調整。

在我的假例子（用戶按1,2，然後3），它創建了一個：

cdh... 
afi... 
adi... 
beg... 
cf... 
adh... 
cd... 
afg... 
adg... 
bei... 
ceg... 
bfi... 
cdg... 
beh... 
aeg... 
ce... 
aeh... 
afh... 
bdg... 
bdi... 
cfh... 
ad... 
cdi... 
ceh... 
bfh... 
aei... 
cfi... 
be... 
af... 
bdh... 
bf... 
cfg... 
bfg... 
cei... 
ae... 
bd... 
Set size: 36 

歡迎真正的編碼:)