0

シーケンスの計算に役立つアルゴリズムまたは疑似コードのヒントを探しています。これは一種の順列ですが、固定長ではないため正確ではありません。出力シーケンスは次のようになります。

A
B
C
D
AA
BA
CA
DA
AB
BB
CB
DB
AC
BC
CC
DC
AD
BD
CD
DD
AAA
BAA
CAA
DAA
...

上記のすべての文字は実際には整数を表し、最小値から最大値まで増加します。始めてみると深さが分からないので、ネストされた for ループを複数使っただけではうまくいきません。

ここドイツはもう遅いので、このことについて頭を悩ませることはできません。for ループと再帰を使用して実行できることは確かですが、現在、開始方法についての手がかりがありません。

何か案は？

編集: B タイプミスが修正されました。

4

5 に答える 5

1

長さ1、2、3などの4つの異なる数字のすべての組み合わせを使用しているようで、繰り返しが可能です。

長さ 1 から始めます: { A, B, C, D }

長さ 2 を取得するには、長さ 1 のすべてのメンバーの前に A、B、C、D を順番に追加します (16 要素)。

長さ 3 を取得するには、A、B、C、D を長さ 2 のすべてのメンバーの前に順番に追加します (64 要素)。

長さ 4 を取得するには、長さ 3 のすべてのメンバーの前に A、B、C、D を順番に追加します (256 要素)。

等々。

桁数が多い場合も少ない場合も、同じ方法が機能します。たとえば、A が B に等しくなるようにすると、少し複雑になりますが、現在行っていることとは異なります。

于 2012-09-14T23:54:31.777 に答える
0

4つの要素があり、基数4の逆表記で数値をループしているだけです。A = 0、B = 1、C = 2、D = 3と言います：
1桁で0から3までの最初のループ
2桁で00から33までの2番目のループ
など

i    reversed i    output using A,B,C,D digits
loop on 1 digit
0    0             A
1    1             B
2    2             C
3    3             D

loop on 2 digits
00   00            AA
01   10            BA
02   20            CA
03   30            DA
10   01            AB
11   11            BB
12   21            CB
13   31            DB
20   02            AC
21   12            BC
22   22            CC
...

アルゴリズムはかなり明白です。筋肉束3aTAOCPD. KnuthのアルゴリズムL（辞書式t-combination生成）を見ることができます。

于 2012-09-15T00:12:32.523 に答える
0

どうですか：

  Private Sub DoIt(minVal As Integer, maxVal As Integer, maxDepth As Integer)
    If maxVal < minVal OrElse maxDepth <= 0 Then
      Debug.WriteLine("no results!")
      Return
    End If
    Debug.WriteLine("results:")

    Dim resultList As New List(Of Integer)(maxDepth)

    ' initialize with the 1st result: this makes processing the remainder easy to write.
    resultList.Add(minVal)
    Dim depthIndex As Integer = 0
    Debug.WriteLine(CStr(minVal))

    Do

      ' find the term to be increased
      Dim indexOfTermToIncrease As Integer = 0
      While resultList(indexOfTermToIncrease) = maxVal

        resultList(indexOfTermToIncrease) = minVal

        indexOfTermToIncrease += 1
        If indexOfTermToIncrease > depthIndex Then
          depthIndex += 1
          If depthIndex = maxDepth Then
            Return
          End If
          resultList.Add(minVal - 1)
          Exit While
        End If
      End While

      ' increase the term that was identified
      resultList(indexOfTermToIncrease) += 1

      ' output
      For d As Integer = 0 To depthIndex
        Debug.Write(CStr(resultList(d)) + " ")
      Next
      Debug.WriteLine("")

    Loop

  End Sub

それで十分でしょうか？多くのメモリを必要とせず、比較的高速です (出力への書き込みを除けば...)。

于 2012-09-15T14:21:05.980 に答える
0

OPからのコメントに基づいて、リストを保存せずにシーケンスを実行する方法を次に示します。

オドメーターの類推を使用します。これには、インデックスを追跡するだけで済みます。シーケンスの最初のメンバーが循環するたびに、1 つ右にインクリメントします。シーケンスのそのメンバーが循環するのがこれが初めての場合は、メンバーをシーケンスに追加します。

増分はカスケードする必要があります。これは、99,999 マイルから 100,000 マイルに移動するのと同じです (コンマは千のマーカーです)。

1000 個の整数を循環させる必要がある場合は、上記の 10 を基数とするのではなく、1000 を基数とする走行距離計を見ているふりをしてください。

于 2012-09-15T00:17:32.987 に答える
0

あなたのシーケンスは (A n-1 XA T )のように見えます。ここで、 A は行列であり、 A Tはその転置です。

A= [A,B,C,D]

A T XA n-1 ∀ (n=0)

シーケンス= A、B、C、D

A T XA n-1 ∀ (n=2)

シーケンス= AA、BA、CA、DA、AB、BB、CB、DB、AC、BC、CC、DC、AD、BD、CD、DD

このような行列乗算コードを使用して、必要なものを実装できます。

于 2012-09-14T23:48:42.233 に答える