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 等的四个不同数字的所有组合，允许重复。

所以从长度 1 开始：{ A, B, C, D }

要获得长度 2，将 A、B、C、D 依次添加到长度为 1 的每个成员之前。（16 个元素）

要获得长度 3，将 A、B、C、D 依次添加到长度为 2 的每个成员之前。（64 个元素）

要获得长度 4，将 A、B、C、D 依次添加到长度为 3 的每个成员之前。（256 个元素）

等等。

如果您有更多或更少的数字，则相同的方法将起作用。如果你允许 A 等于 B，它会变得有点棘手，但这看起来不像你现在正在做的事情。

于 2012-09-14T23:54:31.777 回答
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 回答
0

你有 4 个元素，你只是在一个反向的 base 4 表示法中循环数字。说 A=0,B=1,C=2,D=3 ：
第一个循环从 0 到 3 在 1 位上
第二个循环从 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
...

该算法非常明显。您可以查看分册 3a TAOCP D. Knuth中的算法 L（词典 t 组合生成） 。

于 2012-09-15T00:12:32.523 回答
0

根据 OP 的评论，这是一种在不存储列表的情况下执行序列的方法。

使用里程表类比。这只需要跟踪索引。每次序列的第一个成员循环时，向右递增一个。如果这是该序列的成员第一次循环，则将成员添加到序列中。

增量将需要级联。这相当于从 99,999 英里到 100,000 英里（逗号是千位标记）。

如果你有一千个整数需要循环遍历，那么假设你正在查看以 1000 为基数的里程表，而不是上述以 10 为基数的里程表。

于 2012-09-15T00:17:32.987 回答
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 回答