Как мы можем найти все расположения строки длиной 5 символов?

Question

Как мы можем найти все расположения строки длиной 5 символов?

Используя 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.

У меня есть пример кода, я не уверен, так как он неполон, и мне интересно, правильно ли я это делаю.

2

cobol

Источник

user1515129 06 авг '13 в 07:15

4 ответа


                    
                        
                                         
                            
                                
                                    
                                        
                                            Когда "значение 1" зафиксировано в первой позиции, пройдите через цикл один раз, генерируя 24 сочетания.
Затем "сначала выделив место для него", поместите значение 1 в столбец 2. Затем значение 1 в столбец 3. Столбец 4. Столбец 5.
Или же
Возьмите начальные результаты, это один набор, затем "поверните" все значения в результатах (1 = 2, 2 = 3, 3 = 4, 4 = 5, 5 = 1). Это второй набор результатов. Сделайте это еще три раза.
С помощью любого из них вы можете включить "полные результаты" из одной итерации, чтобы получить "шаблон" из 24 результатов.
Например, в код Валдиса Гринбергса можно добавить следующее:
В РАЗДЕЛЕ РАБОТЫ-ХРАНЕНИЯ:
01  SAVE-SOLUTION.
    02  SAVE-IT                 PIC X.
    02  FILLER                  PIC X(4).
В ПРОЦЕДУРЕ ОТДЕЛА:
Измените первый PERFORM на
MOVE 1 TO I
После каждого РЕШЕНИЯ отображается:
PERFORM SOLUTIONS-FOR-REMAINING-VALUES
Что для версии "вставка столбца":
   SOLUTIONS-FOR-REMAINING-VALUES.
       MOVE SOLUTION                TO SAVE-SOLUTION
       MOVE SOLUTION (2:1)          TO SOLUTION (1:1)
       MOVE SAVE-IT                 TO SOLUTION (2:1) 
       ADD 1                        TO SOLUTION-COUNT 
       DISPLAY SOLUTION 
       MOVE SAVE-SOLUTION           TO SOLUTION
       MOVE SOLUTION (3:1)          TO SOLUTION (1:1)
       MOVE SAVE-IT                 TO SOLUTION (3:1) 
       ADD 1                        TO SOLUTION-COUNT 
       DISPLAY SOLUTION 
       MOVE SAVE-SOLUTION           TO SOLUTION
       MOVE SOLUTION (4:1)          TO SOLUTION (1:1)
       MOVE SAVE-IT                 TO SOLUTION (4:1) 
       ADD 1                        TO SOLUTION-COUNT 
       DISPLAY SOLUTION 
       MOVE SAVE-SOLUTION           TO SOLUTION
       MOVE SOLUTION (5:1)          TO SOLUTION (1:1)
       MOVE SAVE-IT                 TO SOLUTION (5:1) 
       ADD 1                        TO SOLUTION-COUNT 
       DISPLAY SOLUTION 
       .
И для версии с "повторяющимся транспонированием":
   SOLUTIONS-FOR-REMAINING-VALUES.
       PERFORM 4 TIMES
           MOVE SOLUTION (1:1) TO SAVE-IT
           MOVE SOLUTION (2:1) TO SOLUTION (1:1)
           MOVE SOLUTION (3:1) TO SOLUTION (2:1)
           MOVE SOLUTION (4:1) TO SOLUTION (3:1)
           MOVE SOLUTION (5:1) TO SOLUTION (4:1)
           MOVE SAVE-IT TO SOLUTION (5:1)
           ADD 1 TO SOLUTION-COUNT 
           DISPLAY SOLUTION 
       END-PERFORM
       .
Конечно, абзац, который я добавил, можно сделать в виде цикла, но я хочу сосредоточиться на том, чтобы показать, что происходит, а не на том, как написать цикл в COBOL.
Два разных "решения" - это две реализации одного и того же. Как только "шаблон" установлен, другие 4/5 выходных данных могут быть сгенерированы простым изменением содержимого в фиксированном шаблоне.
Циклы в исходном коде могут быть обработаны.
Если для реального приложения производительность является основным требованием, просто поймите, что "шаблон" известен до того, как будет написана строка кода. Код просто спасает вас от написания 24 результатов вручную. Для производительности и с достаточно маленьким "шаблоном" просто закодируйте его, забудьте про циклы.
И я бы не стал использовать всю "референсную модификацию" сам, я просто оставил ее там с оригинала.
Теперь две версии без циклов. Основываясь на том факте, что "шаблон" для первых 24 решений известен заранее, и что остальные решения (уже известные, но не нуждающиеся в одинаковом кодировании) могут быть легко получены из тот.
Вращающиеся значения.
ID DIVISION.
PROGRAM-ID. PROTATE.
DATA DIVISION.
WORKING-STORAGE SECTION.
01  CHAR-SET                    PIC X(5) VALUE 'ABCDE'.
01  SOLUTION                    PIC X(5).
01  SOLUTION-COUNT     binary   PIC 9(4) VALUE ZERO.
01  INDEXES.
    02  COLUMN-1              binary         PIC 9(4).
    02  COLUMN-2              binary         PIC 9(4).
    02  COLUMN-3              binary         PIC 9(4).
    02  COLUMN-4              binary         PIC 9(4).
    02  COLUMN-5              binary         PIC 9(4).
    02  ICOL-3                binary         PIC 9(4).
    02  ICOL-4                binary         PIC 9(4).
    02  ICOL-5                binary         PIC 9(4).
01  SAVE-SOLUTION.
    02  SAVE-IT                 PIC X.
    02  FILLER                  PIC X(4).

PROCEDURE DIVISION.
MAIN-para.
    MOVE 1 TO COLUMN-1 
    MOVE 2 TO COLUMN-2
    MOVE 3 TO ICOL-3
    MOVE 4 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 3 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 4 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 4 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 3 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 5 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 3 TO ICOL-4
    MOVE 4 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    DISPLAY SOLUTION-COUNT
    STOP RUN
    .
SIX-SOLUTIONS.
    MOVE ICOL-3 TO COLUMN-3
    MOVE ICOL-4 TO COLUMN-4
    MOVE ICOL-5 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-4
    MOVE ICOL-4 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-4 TO COLUMN-3
    MOVE ICOL-3 TO COLUMN-4
    MOVE ICOL-5 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-4
    MOVE ICOL-3 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-3
    MOVE ICOL-3 TO COLUMN-4
    MOVE ICOL-4 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-4 TO COLUMN-4
    MOVE ICOL-3 TO COLUMN-5
    PERFORM A-SOLUTION
    .
A-SOLUTION.
    MOVE CHAR-SET ( 1 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE CHAR-SET ( COLUMN-2 : 1 ) TO SOLUTION ( 2 : 1 )
    MOVE CHAR-SET ( COLUMN-3 : 1 ) TO SOLUTION ( 3 : 1 )
    MOVE CHAR-SET ( COLUMN-4 : 1 ) TO SOLUTION ( 4 : 1 )
    MOVE CHAR-SET ( COLUMN-5 : 1 ) TO SOLUTION ( 5 : 1 )
    PERFORM SOLUTION-READY
    PERFORM SOLUTIONS-FOR-REMAINING-VALUES
    .
SOLUTIONS-FOR-REMAINING-VALUES.
    MOVE SOLUTION TO SAVE-SOLUTION
    MOVE SOLUTION ( 2 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 2 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 3 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 3 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 4 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 4 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 5 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 5 : 1 ) 
    PERFORM SOLUTION-READY
    .
SOLUTION-READY.
    ADD 1 TO SOLUTION-COUNT 
    DISPLAY SOLUTION 
    .
Вставка столбца:
ID DIVISION.
PROGRAM-ID. PCOLINS.
DATA DIVISION.
WORKING-STORAGE SECTION.
01  CHAR-SET                    PIC X(5) VALUE 'ABCDE'.
01  SOLUTION                    PIC X(5).
01  SOLUTION-COUNT     binary   PIC 9(4) VALUE ZERO.
01  INDEXES.
    02  COLUMN-1              binary         PIC 9(4).
    02  COLUMN-2              binary         PIC 9(4).
    02  COLUMN-3              binary         PIC 9(4).
    02  COLUMN-4              binary         PIC 9(4).
    02  COLUMN-5              binary         PIC 9(4).
    02  ICOL-3                binary         PIC 9(4).
    02  ICOL-4                binary         PIC 9(4).
    02  ICOL-5                binary         PIC 9(4).
01  SAVE-SOLUTION.
    02  SAVE-IT                 PIC X.
    02  FILLER                  PIC X(4).     

PROCEDURE DIVISION.
MAIN-para.
    MOVE 1 TO COLUMN-1 
    MOVE 2 TO COLUMN-2
    MOVE 3 TO ICOL-3
    MOVE 4 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 3 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 4 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 4 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 3 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 5 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 3 TO ICOL-4
    MOVE 4 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    DISPLAY SOLUTION-COUNT
    STOP RUN
    .
SIX-SOLUTIONS.
    MOVE ICOL-3 TO COLUMN-3
    MOVE ICOL-4 TO COLUMN-4
    MOVE ICOL-5 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-4
    MOVE ICOL-4 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-4 TO COLUMN-3
    MOVE ICOL-3 TO COLUMN-4
    MOVE ICOL-5 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-4
    MOVE ICOL-3 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-3
    MOVE ICOL-3 TO COLUMN-4
    MOVE ICOL-4 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-4 TO COLUMN-4
    MOVE ICOL-3 TO COLUMN-5
    PERFORM A-SOLUTION
    .
A-SOLUTION.
    MOVE CHAR-SET ( 1 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE CHAR-SET ( COLUMN-2 : 1 ) TO SOLUTION ( 2 : 1 )
    MOVE CHAR-SET ( COLUMN-3 : 1 ) TO SOLUTION ( 3 : 1 )
    MOVE CHAR-SET ( COLUMN-4 : 1 ) TO SOLUTION ( 4 : 1 )
    MOVE CHAR-SET ( COLUMN-5 : 1 ) TO SOLUTION ( 5 : 1 )
    PERFORM SOLUTION-READY
    PERFORM SOLUTIONS-FOR-REMAINING-VALUES
    .
SOLUTIONS-FOR-REMAINING-VALUES.
    MOVE SOLUTION TO SAVE-SOLUTION
    MOVE SOLUTION ( 2 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 2 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 3 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 3 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 4 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 4 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 5 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 5 : 1 ) 
    PERFORM SOLUTION-READY
    .
SOLUTION-READY.
    ADD 1 TO SOLUTION-COUNT 
    DISPLAY SOLUTION 
    .
ХОРОШО. Конкретная программа для вопроса. Вроде, как бы, что-то вроде. Ожидаемый ответ, вероятно, будет Ingo/Valdis Grinbergs, чтобы узнать, как "вкладывать" петли.
Что делает программа? Что ж, он получает 1/5 перестановок, а затем полагается на симметрию в этих результатах, чтобы генерировать оставшиеся 4/5 перестановок без дальнейшей обработки после перестановки.
Почему нет петель? Потому что, поскольку он известен заранее, ответ известен заранее. Вместо циклов, которые неизменно дают один и тот же результат, результат был "жестко запрограммирован".
Могут ли программы быть обобщенными? Да. Какой алгоритм?
Ну, вы могли бы описать код и решить, как его расширить. Или вы можете посмотреть на данные.
Генерация шести пар из двух делает что? Ну, пары из двух - это просто перестановки двух значений. Шесть, перестановки трех значений. Делать шесть четыре раза - это перестановки четырех значений.
Итак, для подстановки пяти значений примените каждое из пяти отдельных значений к шаблону перестановки из четырех значений. Чтобы ввести четыре значения, примените каждое из четырех отдельных значений к шаблону перестановки из трех значений. Чтобы переставить три значения, примените каждое из трех отдельных значений к шаблону перестановки двух значений. Чтобы переставить два значения, примените каждое из двух отдельных значений к шаблону перестановки одного значения (!).
Таким образом, для значений N perm примените каждое из N отдельных значений к шаблону перестановки (N-1) значений.
В общем решении N = 1 требует нулевых итераций. N = 2 требует одной итерации. N = 3 требует двух итераций. N = 4 требует шести итераций. N = 5 требует 24 итераций. N = N требует (N - 1)! итераций, с N = 1 частный случай.
Для генерации всех данных, а не для начального решения с жестким кодом, требуется сумма. N = 5, от начальной точки недоступных меньших перестановок, требуется 24 + 6 + 2 + 1 = 33 итерации.
И да, это легко поддается рекурсии для решения. Это также поддается решению без петель вообще. Это не специфично для COBOL, но то же самое для любого языка.
Конечно, вам никогда не понадобится более одного вызова на программу для разных значений N. Итак, еще раз, нет проблем с использованием рекурсии.
Проблема с рекурсией в COBOL заключается в том, что программисты на COBOL не знают, как это сделать.
Очевидное использование для "гладкой" версии - это когда приходится иметь дело с N "большого" размера (факториалы задействованы, поэтому "большой" приходит довольно быстро).
Другое дело, "ясность". Может ли следующий человек понять, что делает код?
Я сделаю "хорошую" версию, если найду время..,
                                        
                                    
                                
                                
                                    
                                        
                                            
                                                
                                                    1
                                                    
                                                
                                            
                                        
                                        
                                    
                                    
                                        
                                            
                                                Источник
                                                                                        
                                            Поделиться
                                        
                                        
                                            
                                                
                                                    user1927206
                                                                                                    
                                            
                                             07 авг '13 в 08:06
                                            2013-08-07 08:06
                                        
                                    
                                
                                2013-08-07 08:06
                            
                        
                    
                        
                                         
                            
                                
                                    
                                        
                                            ИМХО, вам понадобится n-кратный вложенный цикл, чтобы сделать перестановки из n элементов. Следующее обеспечивает план:
for i = 1 to 5
  for j = 1 to 5 if j != i
    for k = 1 to 5 if k != j && k != i
      for m = 1 to 5 if m != k && m != j && m != i
        for n = 1 to 5 if n != m && n != k && n != j && n != i
          solution = (i,j,k,m,n)
Таким образом, вы получите 120 решений. Если это необходимо, вы можете заменить индексы фактическими символами в соответствующих позициях.
Для ее решения с помощью SQL предполагается, что у нас есть таблица с 5 различными строками:
CREATE NUMBERS (VAL INT PRIMARY KEY);
INSERT INTO NUMBERS VALUES(1);
INSERT INTO NUMBERS VALUES(2);
INSERT INTO NUMBERS VALUES(3);
INSERT INTO NUMBERS VALUES(4);
INSERT INTO NUMBERS VALUES(5);
SELECT VAL I, VAL J, VAL K, VAL M, VAL N FROM NUMBERS WHERE
    I <> J 
    AND K <> I AND K <> J
    AND M <> I AND M <> J AND M <> K
    AND N <> I AND N <> J AND N <> K AND N <> M;
Не уверен, что синтаксис SQL правильный, но вы поняли идею.
                                        
                                    
                                
                                
                                    
                                        
                                            
                                                
                                                    1
                                                    
                                                
                                            
                                        
                                        
                                    
                                    
                                        
                                            
                                                Источник
                                                                                        
                                            Поделиться
                                        
                                        
                                            
                                                
                                                    user86604
                                                                                                    
                                            
                                             06 авг '13 в 11:52
                                            2013-08-06 11:52
                                        
                                    
                                
                                2013-08-06 11:52
                            
                        
                                 

                    
    
        
        
    


                    
                    

                    
    
                
    

                    
                    
                        
                            
                                Другие вопросы по тегам
                                


    cobol

user192510 07 авг '13 в 15:00 2013-08-07 15:00 · Answer 1 · 2013-08-07 15:00

Эта проблема может быть решена с использованием практически любого языка программирования (включая COBOL), с рекурсией или без нее. Рекурсивное решение тривиально, нерекурсивное решение немного интереснее. Вот COBOL, нерекурсивная реализация.

Несколько замечаний:

Договоренности могут быть построены итеративно из пустого базового случая и списка символов, из которых строятся договоренности. На каждой итерации следующий символ берется из списка ввода и вставляется во все возможные позиции базовых вариантов из предыдущей итерации. Эти новые строки становятся базовым вариантом для следующей итерации. Когда список ввода становится пустым, базовый случай содержит все возможные меры.

Рассмотрим построение трех символов следующим образом:

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]]

Обратите внимание, что количество строк в конечном базовом случае равно факториалу (длина (входная)). В приведенном выше примере три символа были введены, давая 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
       .

Заключительное примечание: если входная строка содержит повторяющиеся символы, то некоторые из шаблонов будут повторяться. Это решение не принимает во внимание это "осложнение".

user1591657 09 авг '13 в 01:14 2013-08-09 01:14 · Answer 2 · 2013-08-09 01:14

Вот реализация плана Инго (см. Выше) в языке COBOL. Я предлагаю это, потому что это другой алгоритм, чем те, которые предоставили NealB и Билл Вуджер.



   IDENTIFICATION DIVISION.
   PROGRAM-ID. PERMUTATION.
  * GENERATE PERMUTATIONS FROM A SET OF FIVE ELEMENTS
  * WITHOUT USING RECURSION

   ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
   FILE-CONTROL.

   DATA DIVISION.
   FILE SECTION.

   WORKING-STORAGE SECTION.
   01  CHAR-SET                    PIC X(5) VALUE 'ABCDE'.
   01  SOLUTION                    PIC X(5).
   01  SOLUTION-COUNT              PIC 999 VALUE ZERO.
   01  INDEXES.
       02  I                       PIC 9.
       02  J                       PIC 9.
       02  K                       PIC 9.
       02  L                       PIC 9.
       02  M                       PIC 9.

   PROCEDURE DIVISION.
   MAIN.
  * IGNORED REGULAR INDENTING TO SIMPLIFY CODE
       PERFORM VARYING I FROM 1 BY 1 UNTIL I > 5
       PERFORM VARYING J FROM 1 BY 1 UNTIL J > 5
       IF J NOT = I
       PERFORM VARYING K FROM 1 BY 1 UNTIL K > 5
       IF K NOT = J AND K NOT = I
       PERFORM VARYING L FROM 1 BY 1 UNTIL L > 5
       IF L NOT = K AND L NOT = J AND L NOT = I
       PERFORM VARYING M FROM 1 BY 1 UNTIL M > 5
       IF M NOT = L AND M NOT = K AND M NOT = J AND M NOT = I
            ADD 1 TO SOLUTION-COUNT END-ADD
            DISPLAY SOLUTION-COUNT ' ' WITH NO ADVANCING
            END-DISPLAY
            MOVE CHAR-SET(I:1) TO SOLUTION (1:1)
            MOVE CHAR-SET(J:1) TO SOLUTION (2:1)
            MOVE CHAR-SET(K:1) TO SOLUTION (3:1)
            MOVE CHAR-SET(L:1) TO SOLUTION (4:1)
            MOVE CHAR-SET(M:1) TO SOLUTION (5:1)
            DISPLAY SOLUTION END-DISPLAY
       END-IF
       END-PERFORM
       END-IF
       END-PERFORM
       END-IF
       END-PERFORM
       END-IF
       END-PERFORM
       END-PERFORM
       STOP RUN
       .

user1927206 07 авг '13 в 08:06 2013-08-07 08:06 · Answer 3 · 2013-08-07 08:06

Когда "значение 1" зафиксировано в первой позиции, пройдите через цикл один раз, генерируя 24 сочетания.

Затем "сначала выделив место для него", поместите значение 1 в столбец 2. Затем значение 1 в столбец 3. Столбец 4. Столбец 5.

Или же

Возьмите начальные результаты, это один набор, затем "поверните" все значения в результатах (1 = 2, 2 = 3, 3 = 4, 4 = 5, 5 = 1). Это второй набор результатов. Сделайте это еще три раза.

С помощью любого из них вы можете включить "полные результаты" из одной итерации, чтобы получить "шаблон" из 24 результатов.

Например, в код Валдиса Гринбергса можно добавить следующее:

В РАЗДЕЛЕ РАБОТЫ-ХРАНЕНИЯ:

01  SAVE-SOLUTION.
    02  SAVE-IT                 PIC X.
    02  FILLER                  PIC X(4).

В ПРОЦЕДУРЕ ОТДЕЛА:

Измените первый PERFORM на

MOVE 1 TO I

После каждого РЕШЕНИЯ отображается:

PERFORM SOLUTIONS-FOR-REMAINING-VALUES

Что для версии "вставка столбца":

   SOLUTIONS-FOR-REMAINING-VALUES.
       MOVE SOLUTION                TO SAVE-SOLUTION
       MOVE SOLUTION (2:1)          TO SOLUTION (1:1)
       MOVE SAVE-IT                 TO SOLUTION (2:1) 
       ADD 1                        TO SOLUTION-COUNT 
       DISPLAY SOLUTION 
       MOVE SAVE-SOLUTION           TO SOLUTION
       MOVE SOLUTION (3:1)          TO SOLUTION (1:1)
       MOVE SAVE-IT                 TO SOLUTION (3:1) 
       ADD 1                        TO SOLUTION-COUNT 
       DISPLAY SOLUTION 
       MOVE SAVE-SOLUTION           TO SOLUTION
       MOVE SOLUTION (4:1)          TO SOLUTION (1:1)
       MOVE SAVE-IT                 TO SOLUTION (4:1) 
       ADD 1                        TO SOLUTION-COUNT 
       DISPLAY SOLUTION 
       MOVE SAVE-SOLUTION           TO SOLUTION
       MOVE SOLUTION (5:1)          TO SOLUTION (1:1)
       MOVE SAVE-IT                 TO SOLUTION (5:1) 
       ADD 1                        TO SOLUTION-COUNT 
       DISPLAY SOLUTION 
       .

И для версии с "повторяющимся транспонированием":

   SOLUTIONS-FOR-REMAINING-VALUES.
       PERFORM 4 TIMES
           MOVE SOLUTION (1:1) TO SAVE-IT
           MOVE SOLUTION (2:1) TO SOLUTION (1:1)
           MOVE SOLUTION (3:1) TO SOLUTION (2:1)
           MOVE SOLUTION (4:1) TO SOLUTION (3:1)
           MOVE SOLUTION (5:1) TO SOLUTION (4:1)
           MOVE SAVE-IT TO SOLUTION (5:1)
           ADD 1 TO SOLUTION-COUNT 
           DISPLAY SOLUTION 
       END-PERFORM
       .

Конечно, абзац, который я добавил, можно сделать в виде цикла, но я хочу сосредоточиться на том, чтобы показать, что происходит, а не на том, как написать цикл в COBOL.

Два разных "решения" - это две реализации одного и того же. Как только "шаблон" установлен, другие 4/5 выходных данных могут быть сгенерированы простым изменением содержимого в фиксированном шаблоне.

Циклы в исходном коде могут быть обработаны.

Если для реального приложения производительность является основным требованием, просто поймите, что "шаблон" известен до того, как будет написана строка кода. Код просто спасает вас от написания 24 результатов вручную. Для производительности и с достаточно маленьким "шаблоном" просто закодируйте его, забудьте про циклы.

И я бы не стал использовать всю "референсную модификацию" сам, я просто оставил ее там с оригинала.

Теперь две версии без циклов. Основываясь на том факте, что "шаблон" для первых 24 решений известен заранее, и что остальные решения (уже известные, но не нуждающиеся в одинаковом кодировании) могут быть легко получены из тот.

Вращающиеся значения.

ID DIVISION.
PROGRAM-ID. PROTATE.
DATA DIVISION.
WORKING-STORAGE SECTION.
01  CHAR-SET                    PIC X(5) VALUE 'ABCDE'.
01  SOLUTION                    PIC X(5).
01  SOLUTION-COUNT     binary   PIC 9(4) VALUE ZERO.
01  INDEXES.
    02  COLUMN-1              binary         PIC 9(4).
    02  COLUMN-2              binary         PIC 9(4).
    02  COLUMN-3              binary         PIC 9(4).
    02  COLUMN-4              binary         PIC 9(4).
    02  COLUMN-5              binary         PIC 9(4).
    02  ICOL-3                binary         PIC 9(4).
    02  ICOL-4                binary         PIC 9(4).
    02  ICOL-5                binary         PIC 9(4).
01  SAVE-SOLUTION.
    02  SAVE-IT                 PIC X.
    02  FILLER                  PIC X(4).

PROCEDURE DIVISION.
MAIN-para.
    MOVE 1 TO COLUMN-1 
    MOVE 2 TO COLUMN-2
    MOVE 3 TO ICOL-3
    MOVE 4 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 3 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 4 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 4 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 3 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 5 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 3 TO ICOL-4
    MOVE 4 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    DISPLAY SOLUTION-COUNT
    STOP RUN
    .
SIX-SOLUTIONS.
    MOVE ICOL-3 TO COLUMN-3
    MOVE ICOL-4 TO COLUMN-4
    MOVE ICOL-5 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-4
    MOVE ICOL-4 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-4 TO COLUMN-3
    MOVE ICOL-3 TO COLUMN-4
    MOVE ICOL-5 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-4
    MOVE ICOL-3 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-3
    MOVE ICOL-3 TO COLUMN-4
    MOVE ICOL-4 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-4 TO COLUMN-4
    MOVE ICOL-3 TO COLUMN-5
    PERFORM A-SOLUTION
    .
A-SOLUTION.
    MOVE CHAR-SET ( 1 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE CHAR-SET ( COLUMN-2 : 1 ) TO SOLUTION ( 2 : 1 )
    MOVE CHAR-SET ( COLUMN-3 : 1 ) TO SOLUTION ( 3 : 1 )
    MOVE CHAR-SET ( COLUMN-4 : 1 ) TO SOLUTION ( 4 : 1 )
    MOVE CHAR-SET ( COLUMN-5 : 1 ) TO SOLUTION ( 5 : 1 )
    PERFORM SOLUTION-READY
    PERFORM SOLUTIONS-FOR-REMAINING-VALUES
    .
SOLUTIONS-FOR-REMAINING-VALUES.
    MOVE SOLUTION TO SAVE-SOLUTION
    MOVE SOLUTION ( 2 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 2 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 3 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 3 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 4 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 4 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 5 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 5 : 1 ) 
    PERFORM SOLUTION-READY
    .
SOLUTION-READY.
    ADD 1 TO SOLUTION-COUNT 
    DISPLAY SOLUTION 
    .

Вставка столбца:

ID DIVISION.
PROGRAM-ID. PCOLINS.
DATA DIVISION.
WORKING-STORAGE SECTION.
01  CHAR-SET                    PIC X(5) VALUE 'ABCDE'.
01  SOLUTION                    PIC X(5).
01  SOLUTION-COUNT     binary   PIC 9(4) VALUE ZERO.
01  INDEXES.
    02  COLUMN-1              binary         PIC 9(4).
    02  COLUMN-2              binary         PIC 9(4).
    02  COLUMN-3              binary         PIC 9(4).
    02  COLUMN-4              binary         PIC 9(4).
    02  COLUMN-5              binary         PIC 9(4).
    02  ICOL-3                binary         PIC 9(4).
    02  ICOL-4                binary         PIC 9(4).
    02  ICOL-5                binary         PIC 9(4).
01  SAVE-SOLUTION.
    02  SAVE-IT                 PIC X.
    02  FILLER                  PIC X(4).     

PROCEDURE DIVISION.
MAIN-para.
    MOVE 1 TO COLUMN-1 
    MOVE 2 TO COLUMN-2
    MOVE 3 TO ICOL-3
    MOVE 4 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 3 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 4 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 4 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 3 TO ICOL-4
    MOVE 5 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    MOVE 5 TO COLUMN-2
    MOVE 2 TO ICOL-3
    MOVE 3 TO ICOL-4
    MOVE 4 TO ICOL-5
    PERFORM SIX-SOLUTIONS
    DISPLAY SOLUTION-COUNT
    STOP RUN
    .
SIX-SOLUTIONS.
    MOVE ICOL-3 TO COLUMN-3
    MOVE ICOL-4 TO COLUMN-4
    MOVE ICOL-5 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-4
    MOVE ICOL-4 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-4 TO COLUMN-3
    MOVE ICOL-3 TO COLUMN-4
    MOVE ICOL-5 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-4
    MOVE ICOL-3 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-5 TO COLUMN-3
    MOVE ICOL-3 TO COLUMN-4
    MOVE ICOL-4 TO COLUMN-5
    PERFORM A-SOLUTION
    MOVE ICOL-4 TO COLUMN-4
    MOVE ICOL-3 TO COLUMN-5
    PERFORM A-SOLUTION
    .
A-SOLUTION.
    MOVE CHAR-SET ( 1 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE CHAR-SET ( COLUMN-2 : 1 ) TO SOLUTION ( 2 : 1 )
    MOVE CHAR-SET ( COLUMN-3 : 1 ) TO SOLUTION ( 3 : 1 )
    MOVE CHAR-SET ( COLUMN-4 : 1 ) TO SOLUTION ( 4 : 1 )
    MOVE CHAR-SET ( COLUMN-5 : 1 ) TO SOLUTION ( 5 : 1 )
    PERFORM SOLUTION-READY
    PERFORM SOLUTIONS-FOR-REMAINING-VALUES
    .
SOLUTIONS-FOR-REMAINING-VALUES.
    MOVE SOLUTION TO SAVE-SOLUTION
    MOVE SOLUTION ( 2 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 2 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 3 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 3 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 4 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 4 : 1 ) 
    PERFORM SOLUTION-READY
    MOVE SAVE-SOLUTION TO SOLUTION
    MOVE SOLUTION ( 5 : 1 ) TO SOLUTION ( 1 : 1 )
    MOVE SAVE-IT TO SOLUTION ( 5 : 1 ) 
    PERFORM SOLUTION-READY
    .
SOLUTION-READY.
    ADD 1 TO SOLUTION-COUNT 
    DISPLAY SOLUTION 
    .

ХОРОШО. Конкретная программа для вопроса. Вроде, как бы, что-то вроде. Ожидаемый ответ, вероятно, будет Ingo/Valdis Grinbergs, чтобы узнать, как "вкладывать" петли.

Что делает программа? Что ж, он получает 1/5 перестановок, а затем полагается на симметрию в этих результатах, чтобы генерировать оставшиеся 4/5 перестановок без дальнейшей обработки после перестановки.

Почему нет петель? Потому что, поскольку он известен заранее, ответ известен заранее. Вместо циклов, которые неизменно дают один и тот же результат, результат был "жестко запрограммирован".

Могут ли программы быть обобщенными? Да. Какой алгоритм?

Ну, вы могли бы описать код и решить, как его расширить. Или вы можете посмотреть на данные.

Генерация шести пар из двух делает что? Ну, пары из двух - это просто перестановки двух значений. Шесть, перестановки трех значений. Делать шесть четыре раза - это перестановки четырех значений.

Итак, для подстановки пяти значений примените каждое из пяти отдельных значений к шаблону перестановки из четырех значений. Чтобы ввести четыре значения, примените каждое из четырех отдельных значений к шаблону перестановки из трех значений. Чтобы переставить три значения, примените каждое из трех отдельных значений к шаблону перестановки двух значений. Чтобы переставить два значения, примените каждое из двух отдельных значений к шаблону перестановки одного значения (!).

Таким образом, для значений N perm примените каждое из N отдельных значений к шаблону перестановки (N-1) значений.

В общем решении N = 1 требует нулевых итераций. N = 2 требует одной итерации. N = 3 требует двух итераций. N = 4 требует шести итераций. N = 5 требует 24 итераций. N = N требует (N - 1)! итераций, с N = 1 частный случай.

Для генерации всех данных, а не для начального решения с жестким кодом, требуется сумма. N = 5, от начальной точки недоступных меньших перестановок, требуется 24 + 6 + 2 + 1 = 33 итерации.

И да, это легко поддается рекурсии для решения. Это также поддается решению без петель вообще. Это не специфично для COBOL, но то же самое для любого языка.

Конечно, вам никогда не понадобится более одного вызова на программу для разных значений N. Итак, еще раз, нет проблем с использованием рекурсии.

Проблема с рекурсией в COBOL заключается в том, что программисты на COBOL не знают, как это сделать.

Очевидное использование для "гладкой" версии - это когда приходится иметь дело с N "большого" размера (факториалы задействованы, поэтому "большой" приходит довольно быстро).

Другое дело, "ясность". Может ли следующий человек понять, что делает код?

Я сделаю "хорошую" версию, если найду время..,

user86604 06 авг '13 в 11:52 2013-08-06 11:52 · Answer 4 · 2013-08-06 11:52

ИМХО, вам понадобится n-кратный вложенный цикл, чтобы сделать перестановки из n элементов. Следующее обеспечивает план:

for i = 1 to 5
  for j = 1 to 5 if j != i
    for k = 1 to 5 if k != j && k != i
      for m = 1 to 5 if m != k && m != j && m != i
        for n = 1 to 5 if n != m && n != k && n != j && n != i
          solution = (i,j,k,m,n)

Таким образом, вы получите 120 решений. Если это необходимо, вы можете заменить индексы фактическими символами в соответствующих позициях.

Для ее решения с помощью SQL предполагается, что у нас есть таблица с 5 различными строками:

CREATE NUMBERS (VAL INT PRIMARY KEY);
INSERT INTO NUMBERS VALUES(1);
INSERT INTO NUMBERS VALUES(2);
INSERT INTO NUMBERS VALUES(3);
INSERT INTO NUMBERS VALUES(4);
INSERT INTO NUMBERS VALUES(5);
SELECT VAL I, VAL J, VAL K, VAL M, VAL N FROM NUMBERS WHERE
    I <> J 
    AND K <> I AND K <> J
    AND M <> I AND M <> J AND M <> K
    AND N <> I AND N <> J AND N <> K AND N <> M;

Не уверен, что синтаксис SQL правильный, но вы поняли идею.