Permutations / Combinations using ABAP

I had written a code in SCN Discussion started by Kiran Premlal to calculate all possible permutations.

The code in this document has certain improvements like:

1. Choose permutation or combination using radio-button
2. Separation of data from logic
3. Minimum and maximum set size can be specified

Why was data separated from logic?

Let us look at some example sets.

 SET 1 SET 2 SET 3 54 apple 1 23 orange 2 101 banana 3

As we can see, sets can be of integers, strings, mixed data types and data can be unsorted.

However, for calculation of output, all we need is a set of indexes.

For index combination {2,3}, subset of SET 1 would be {23, 101}, whereas subset of SET 2 would be {orange, banana}

The code first calculates a list of index combinations, which can then be used to build data sets.

Example Explanation

We look at SET 2 and see how output is being calculated.

 INDEX DATA 1 apple 2 orange 3 banana

Permutation of all pairs

We have 2 slots to fill, and first element can reserve a slot for starters.

Data sets are {apple, orange} and {apple, banana}.

Index set equivalents would be {1, 2} and {1, 3}.

Program would calculate index sets as:

 1 2 1 3 2 1 2 3 3 1 3 2

When these indexes are replaced by their data equivalents, result would be:

 apple orange apple banana orange apple orange banana banana apple banana orange

Combinations of all singles and pairs

Keeping above SET 2 as input data, we see how output is calculated.

For calculating singles and pairs, we have minimum set size = 1 and maximum set size = 2.

We first find all sets of size 1, and of size 2.

Output in index as well data form would be:

 1 apple 2 orange 3 banana 1 2 apple orange 1 3 apple banana 2 3 orange banana

For same input data, 6 permutation of pairs was calculated, whereas only 3 combination of pairs.

Screenshots from program

The dataset in program is build using characters starting from 'B'.

For dataset of size 3, program would build internal table of characters B, C and D.

 INDEX DATA 1 B 2 C 3 D

We specify in program selection the size of dataset, max/min size of set, and option to find permutation or combination.

Program would store resulting sets in internal table GT_SETS, whose record is capable of storing table of integers.

Although this program prints the resulting sets, minor changes can be done to return the results to another routine.

Code Snippet

1. TYPES: tty TYPE TABLE OF i.
2. * store superset
3. DATA gt_superset_index TYPE TABLE OF i.
4. DATA gt_superset_data TYPE TABLE OF c.
5. * temporarily store set
6. DATA gt_set TYPE TABLE OF i.
7. * gt_sets to store list of sets
8. DATA gt_sets LIKE TABLE OF gt_set.
9. DATA gv_setsize TYPE i.
10. PARAMETERS: p_total TYPE i DEFAULT 5,     "total number of elements in superset
13.       p_max TYPE i DEFAULT 3,       "maximum size of set
14.       p_min TYPE i DEFAULT 1.       "minimum size of set
15. CHECK p_total GT 0 AND
16.     p_max GT 0 AND
17.     p_min GT 0 AND
18.     p_total GE p_max AND
19.     p_max GE p_min.
20. * populate superset index and data
21. DO p_total TIMES.
22.   APPEND sy-index TO gt_superset_index.
23.   APPEND sy-abcde+sy-index(1) TO gt_superset_data.
24. ENDDO.
25. * populate gt_sets table with various combinations of indexes
26. gv_setsize = p_min.
27. WHILE gv_setsize LE p_max.
28.   PERFORM build_sets USING  gt_superset_index
29.               gv_setsize.
30.   gv_setsize = gv_setsize + 1.
31. ENDWHILE.
32. * display sets by using data from gt_superset_data and index from gt_sets
33. PERFORM display.
34. *&---------------------------------------------------------------------*
35. *&      Form  BUILD_SETS
36. *&---------------------------------------------------------------------*
37. FORM build_sets  USING    pt TYPE tty
38.               p_setsize TYPE i.
39.   DATA lv TYPE i.
40.   DATA lv_lines TYPE i.
41.   DATA lt TYPE tty.
42.   DATA lv_tabix TYPE i.
43.   LOOP AT pt INTO lv.
44.   lv_tabix = sy-tabix.
45. * PUSH element to stack and pass remaining to recursive call
46.   APPEND lv TO gt_set.
47. * save set if set size is achieved
48.   DESCRIBE TABLE gt_set LINES lv_lines.
49.   IF lv_lines EQ p_setsize.
50.     APPEND gt_set TO gt_sets.
51.     DELETE gt_set INDEX lv_lines.
52.     CONTINUE.
53.   ENDIF.
54. * recursive call for subset
55.   lt = pt.
56.   CASE 'X'.
57.     WHEN p_perm.
58.     "permutation - calculate for all elements excluding current
59.     DELETE lt INDEX lv_tabix.
60.     WHEN p_comb.
61.     "combination - calculate for all elements following current
62.     DELETE lt TO lv_tabix.
63.   ENDCASE.
64.   IF lt IS NOT INITIAL.
65.     PERFORM build_sets USING  lt
66.                 p_setsize.
67.   ENDIF.
68. * POP the element from stack once all combinations are tried
69.   DESCRIBE TABLE gt_set LINES lv_lines.
70.   DELETE gt_set INDEX lv_lines.
71.   ENDLOOP.
72. ENDFORM.                    " BUILD_SETS
73. *&---------------------------------------------------------------------*
74. *&      Form  DISPLAY
75. *&---------------------------------------------------------------------*
76. FORM display .
77.   FIELD-SYMBOLS: <fs_set> TYPE ANY TABLE,
78.          <fs_index> TYPE i,
79.          <fs_data>  TYPE c.
80.   LOOP AT gt_sets ASSIGNING <fs_set>.
81.   NEW-LINE.
82.   LOOP AT <fs_set> ASSIGNING <fs_index>.
83.     READ TABLE gt_superset_data INDEX <fs_index> ASSIGNING <fs_data>.
84.     IF sy-subrc EQ 0.
85.     WRITE <fs_data>.
86.     ENDIF.
87.   ENDLOOP.
88.   ENDLOOP.
89. ENDFORM.                    " DISPLAY