快速生成字符串組合的方法

給出這樣的語法：[1,0][+,-][2,3]這意味着我們需要所有具有1或0作爲第一個字符，+或 - 作爲第二個字符，以及2或3作爲第三個字符的字符串。

所以，這8個可能的組合

1+2 
1+3 
1-2 
1-3 
0+2 
0+3 
0-2 
0-3

我的方法是有效的，但它會得到稍微大的值相當緩慢。我解析上面的語法併爲每個標記創建一個可能值的數組，並將其放入一個數組中。

equation_set = []; 
tokens = [['1','0'],['+','-'],['2','3']] 
// Initialize empty equation_set 
token = tokens.pop(); 
foreach symbol in tokens 
question_set.add(symbol) 

// We now have a question_set = ['1','0'] 
// and tokens = [['+','-']['2','3']] 
// 
// Now we need to fill out the rest of the possible equations 
foreach token in tokens 
    new_question_set = [] 
    foreach symbol in token 
     foreach question in question_set 
      new_question_set.add(question + symbol) 
    question_set = new_question_set

我相信應該給我我想要的結果，但所有這些foreach讓我感到緊張。我現在纔想出了這個算法，但我覺得我錯過了一些明顯的東西。我們正在搞亂combinatorics，所以如果它非常慢，我不會感到驚訝，但感覺這並不是什麼特別的東西。

乾杯！

來源

2012-09-10 PandemoniumSyndicate

你需要一次生成它們嗎？即，您是否需要能夠同時收集包含所有這些信息的集合。 – Wug

如果你需要創建所有組合，你將不得不進行某種形式的嵌套循環。

確保您的迭代中row major order執行（假設你的語言店以行優先順序您的收藏，其中大多數但不是所有的事）。如果不這樣做可能會對性能產生相當大的影響。

來源

2012-09-10 21:43:30

首先，我不會硬編碼你的答案只有3層。相反，我會建議使用遞歸。

如果遞歸變得太毛茸茸的，你有堆棧溢出比你可以使用動態編程。

，如果你不知道什麼是動態規劃是，比我懷疑你需要使用它的這個問題。

至於效率的話，你將有指數時間複雜不管。這是不可避免的，因爲你也有成倍數量的輸出。

來源

2012-09-10 21:44:43

對於大的情況下，易於編寫遞歸方法可以更快速地引起問題比使用計數器，用於處理所述子集（令牌）和在其中的字符（符號）。

對於令牌3（而不是2，與您的情況相同）和15令牌（而不是3），下面的代碼會生成所需的結果列表（總共3 ** 15 = 14.348,907） 10秒鐘在我不太新的電腦上。

如果適合你的，有像一試（VB：我很快就寫在現有的項目我的工作）：

' decompose input 
Dim allSubSets As New List(Of List(Of Char)) 
Dim subSet As List(Of Char) = Nothing 

For Each c As Char In inputLine 

    Select Case c 
    Case "["c 
     subSet = New List(Of Char) 
    Case "]"c 
     allSubSets.Add(subSet) 
    Case ","c 
     ' just skip 
    Case Else 
     subSet.Add(c) 
    End Select 

Next 

Dim numberOfSubSets As Integer = allSubSets.Count 
Dim subSetLength As Integer = allSubSets(0).Count 

Dim allResults As New List(Of String) 
Dim caseArray(numberOfSubSets - 1) As Char 

' 1st/initialize 
Dim setIndex As Integer 

Dim charIndexes As New List(Of Integer) 
For setIndex = 0 To numberOfSubSets - 1 
    caseArray(setIndex) = allSubSets(setIndex)(0) 
    charIndexes.Add(0) 
Next 
Dim caseResult As New String(caseArray) 
allResults.Add(caseResult) 
Dim resultCount As Long = 1 

' current position 
setIndex = numberOfSubSets - 1 

' do the others 
Do 
    ' if the current subSet is exhausted, track back (iteratively) 
    While (setIndex >= 0) AndAlso (charIndexes(setIndex) = subSetLength - 1) 
    ' and restart the subset we're going the re-access later on 
    charIndexes(setIndex) = 0 
    setIndex -= 1 
    End While 

    ' exit if we're done 
    If setIndex = -1 Then 
    Exit Do 
    End If 

    ' increase counter in the current subset 
    charIndexes(setIndex) += 1 

    ' fill the (remainder of the) case 
    While setIndex < numberOfSubSets 
    caseArray(setIndex) = allSubSets(setIndex)(charIndexes(setIndex)) 
    setIndex += 1 
    End While 
    ' correct the last increment 
    setIndex -= 1 

    ' store result 
    caseResult = New String(caseArray) 
    allResults.Add(caseResult) 
    resultCount += 1 

Loop

其中「inputLine」的格式爲您指定。此外，如果您的代幣的大小不同，您將不得不調整代碼，以便使用正確的代碼大小;我現在假設他們都是平等的。

祝你好運！

來源

2012-09-11 03:01:32

快速生成字符串組合的方法

回答

相關問題