0

今天我们将生成所有可能的数学方程。

给定这样的语法：[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 让我相当紧张。我刚刚弄清楚了这个算法，但我觉得我错过了一些明显的东西。我们正在搞乱组合数学，所以如果它非常慢我不会感到惊讶，但感觉这并没有什么特别的。

干杯!

4

3 回答 3

2

如果您需要创建所有组合，则必须执行某种嵌套循环。

确保您的迭代以行主要顺序执行（假设您的语言以行主要顺序存储您的集合，大多数但不是全部都这样做）。不这样做会对性能产生相当大的影响。

于 2012-09-10T21:43:30.137 回答
0

对于大型情况，易于编写的递归方法可能比使用计数器处理子集（令牌）和其中的字符（符号）更快地导致问题。

对于令牌大小 3（而不是 2，如您的情况）和 15 个令牌（而不是 3），下面的代码在我的大约 10 秒内生成了所需的结果字符串列表（总共 3**15 = 14.348,907）不是那么新的PC。

如果这适合你，试试类似的东西（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-11T03:01:32.717 回答
0

首先，我不会将您的答案硬编码为只有这样的 3 层。相反，我建议使用递归。

如果递归太麻烦并且堆栈溢出，则可以使用动态编程。

如果您不知道什么是动态编程，那么我怀疑您是否需要使用它来解决这个问题。

就效率而言，无论如何，您都将具有指数级的时间复杂度。这是不可避免的，因为您也有大量的输出。

于 2012-09-10T21:44:43.833 回答