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

给出这样的语法：[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

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

回答

相关问题