cobol - 怎样才能找到一个5个字符长的字符串的所有排列呢？

Question

使用 java，查找排列非常简单且可计算。

使用 COBOL 作为编程语言，我发现很难将其编码。

PERFORM VARYING I FROM 1 BY 1 UNTIL I=5
 COMPUTE X = 5-I                        
 PERFORM VARYING J FROM I BY 1 UNTIL J=X
    MOVE WORD(I,1) TO TEMP1.            
    MOVE WORD(J,1) TO TEMP2.            

我有一个代码示例，我不确定，因为它不完整，我想知道我是否采用了正确的方法。

Answer 1

这个问题可以使用任何编程语言(包括 COBOL)来解决，无论是否使用递归。一个递归解决方案很简单，非递归解决方案更有趣一些。这是一个 COBOL 非递归实现。

一些观察:

可以从一个空的基本案例和一个用于构建排列的字符列表迭代地构建排列。在每次迭代中下一个字符从输入列表中取出并插入到先前迭代中基本案例的所有可能位置。这些新字符串成为下一次迭代。当输入列表变空时，基本情况包含所有可能的安排。

考虑以这种方式构建 3 个字符的排列:

Iteration 0 => Input[a, b, c] introduce []: BaseCases[[]]
Iteration 1 => Input[b, c] introduce [a]: BaseCases[[a]]
Iteration 2 => Input[c] introduce [b]: BaseCases[[b a], [a b]]
Iteration 3 => Input [] introduce [c]: BaseCases[[c b a], [b c a], [b a c], [c b a], [b c a], [a b c]]

请注意，最终基本情况中的字符串数等于 factorial(length(input))。在上面的例子中三个字符被介绍送3! = 最终基本情况下的 6 个字符串。

由于在任何给定迭代中要生成的字符串数在迭代时是已知的，并且该数字是比前一次迭代大，我们可以使用相同的数组结构来同时保存两次迭代的基本情况。这是通过从最高下标开始并向后工作构建新的基本案例来完成的。提取时也是如此在先前迭代中生成的基本模式。这解释了为什么完成以下程序中的下标以相反的顺序(倒数而不是倒数)。

   IDENTIFICATION DIVISION.
   PROGRAM-ID ARRANGE.

   DATA DIVISION.
   WORKING-STORAGE SECTION.
   01.
       02 ARRANGEMENT-TABLE.
          03 ARRANGEMENT PIC X(5) OCCURS 120 TIMES.
   01  INPUT-CHARS       PIC X(5) VALUE 'abcde'.
   01  BASE-ARRANGEMENT  PIC X(5).
   01  CURR-CHAR         PIC X.
   01  I                 PIC S9(4) BINARY.
   01  J                 PIC S9(4) BINARY.
   01  K                 PIC S9(4) BINARY.
   01  L                 PIC S9(4) BINARY.
   01  CURR-FACT         PIC S9(9) BINARY.
   01  PREV-FACT         PIC S9(9) BINARY.
   01  COMP-FACT         PIC S9(9) BINARY.
   PROCEDURE DIVISION.
  *
  *    Verify that the Arrangement table is large enough to hold
  *    all possible arrangements of the letters in INPUT-CHARS.
  *
       COMPUTE COMP-FACT =
               FUNCTION FACTORIAL (LENGTH OF INPUT-CHARS)
       IF COMP-FACT > LENGTH OF ARRANGEMENT-TABLE /
                      LENGTH OF ARRANGEMENT(1)
          DISPLAY 'ARRANGEMENT-TABLE is too small.'
          GOBACK
       END-IF
       IF LENGTH OF ARRANGEMENT(1) < LENGTH OF INPUT-CHARS
          DISPLAY 'INPUT-CHARS too long for ARRANGEMENT.'
          GOBACK
       END-IF
       IF LENGTH OF BASE-ARRANGEMENT < LENGTH OF ARRANGEMENT(1)
          DISPLAY 'BASE-ARRANGEMENT is too small for ARRANGEMENT.'
          GOBACK
       END-IF

       MOVE SPACES TO ARRANGEMENT(1)

       DISPLAY 'Starting sequence: ' INPUT-CHARS
  *
  *    Generate all possible arrangements of INPUT-CHARS...
  *
  *       I counts through the set of INPUT-CHARS used in string geneation
  *       J counts down from arrangements built on previous iteration
  *       K counts to number of characters in new expanded base case
  *       L counts down from arrangements to be build in current iteration
  *
  *       CURR-FACT is the factorial of the current iteration number
  *       PREV-FACT is the factorial of the previous iteration
  *       CURR-CHAR is the character to add into existing base cases

       MOVE 1 TO CURR-FACT
       PERFORM VARYING I FROM 1 BY 1
                 UNTIL I > LENGTH OF INPUT-CHARS
          MOVE CURR-FACT TO PREV-FACT
          COMPUTE CURR-FACT = PREV-FACT * I
          MOVE INPUT-CHARS(I:1) TO CURR-CHAR
          MOVE CURR-FACT TO L
          PERFORM VARYING J FROM PREV-FACT BY -1
                    UNTIL J = ZERO
             PERFORM VARYING K FROM 1 BY 1
               UNTIL K > I
               MOVE ARRANGEMENT(J) TO BASE-ARRANGEMENT
               PERFORM NEW-ARRANGEMENT
               COMPUTE L = L - 1
             END-PERFORM
          END-PERFORM
       END-PERFORM
  *
  *    List generated patters...
  *
       COMPUTE COMP-FACT =
               FUNCTION FACTORIAL(LENGTH OF INPUT-CHARS)
       PERFORM VARYING I FROM COMP-FACT BY -1
                 UNTIL I < 1
          DISPLAY ARRANGEMENT(I)
       END-PERFORM
       GOBACK
       .
   NEW-ARRANGEMENT.
  *
  *    Build a new character arrangement by placing
  *    CURR-CHAR into position K of a given
  *    BASE-ARRANGEMENT
  *
       MOVE SPACES    TO ARRANGEMENT(L)
       MOVE CURR-CHAR TO ARRANGEMENT(L)(K:1)
       IF K > 1
          MOVE BASE-ARRANGEMENT(1:K - 1)
            TO ARRANGEMENT(L)(1:K - 1)
       END-IF
       IF K <= PREV-FACT
          MOVE BASE-ARRANGEMENT(K:)
            TO ARRANGEMENT(L)(K + 1:)
       END-IF
       .

最后说明:如果输入字符串包含重复字符，则某些模式将重复。该解决方案没有考虑这种“并发症”。