0

今日は、考えられるすべての数学方程式を生成します。

次のような構文が与えられた場合：[1,0][+,-][2,3]これは、最初の文字として1または0、2番目の文字として+または-、3番目の文字として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つのレイヤーのみを持つように回答をハードコーディングしません。代わりに、再帰を使用することをお勧めします。

再帰があまりにも毛深い場合、動的計画法を使用できるよりもスタックオーバーフローが発生します。

動的計画法が何であるかわからない場合は、この問題にそれを使用する必要があるとは思えません。

効率に関する限り、何があっても時間計算量は指数関数的に複雑になります。これは、出力の数も指数関数的に多いため、避けられません。

于 2012-09-10T21:44:43.833 に答える
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 に答える