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 1SET 2SET 3
54apple1
23orange2
101banana3

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.

INDEXDATA
1apple
2orange
3banana

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:

12
13
21
23
31
32

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

appleorange
applebanana
orangeapple
orangebanana
bananaapple
bananaorange

 

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:

1apple
2orange
3banana
12appleorange
13applebanana
23orangebanana

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.

INDEXDATA
1B
2C
3D

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
  11.       p_perm RADIOBUTTON GROUP r1"permutation
  12.       p_comb RADIOBUTTON GROUP r1"combination
  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