ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

ABAP Advanced String Permutation Generation

ABAP

Goal -- WPM

Ready
Exercise Algorithm Area
1FUNCTION zcl_permutation_generator=>generate_permutations.
2" Generates all unique permutations of a given string.
3" Handles duplicate characters by using a set to track used characters at each level.
4
5DATA: lv_input_string TYPE string VALUE 'aabc'. " Example input
6DATA: lt_permutations TYPE STANDARD TABLE OF string.
7
8CALL METHOD zcl_permutation_generator=>generate_permutations_recursive
9EXPORTING
10iv_current_permutation = ''
11iv_remaining_chars = lv_input_string
12IMPORTING
13et_permutations = lt_permutations.
14
15" Output or process lt_permutations as needed.
16
17ENDFUNCTION.
18
19
20FUNCTION zcl_permutation_generator=>generate_permutations_recursive.
21" Recursive helper function for permutation generation.
22
23" Base case: If no characters remain, add the current permutation to the result.
24IF iv_remaining_chars IS INITIAL.
25APPEND iv_current_permutation TO et_permutations.
26RETURN.
27ENDIF.
28
29" Use a set to keep track of characters already used at this recursion level
30" to avoid generating duplicate permutations when input has duplicate characters.
31DATA: lo_used_chars TYPE REF TO cl_abap_container_utilities=>sorted_table.
32CREATE OBJECT lo_used_chars.
33
34DATA: lv_char TYPE c.
35DATA: lv_index TYPE i.
36DATA: lv_next_permutation TYPE string.
37DATA: lv_next_remaining TYPE string.
38
39DO strlen( iv_remaining_chars ) TIMES.
40lv_index = sy-tabix.
41lv_char = iv_remaining_chars+lv_index(1).
42
43" Check if this character has already been used at this level.
44IF lo_used_chars->exists( lv_char ) = abap_false.
45" Mark character as used for this level.
46lo_used_chars->insert( lv_char ).
47
48" Build the next permutation by appending the current character.
49lv_next_permutation = iv_current_permutation && lv_char.
50
51" Build the remaining characters string by excluding the current character.
52lv_next_remaining = iv_remaining_chars(lv_index) && iv_remaining_chars(lv_index + 1).
53
54" Recursive call.
55CALL METHOD zcl_permutation_generator=>generate_permutations_recursive
56EXPORTING
57iv_current_permutation = lv_next_permutation
58iv_remaining_chars = lv_next_remaining
59IMPORTING
60et_permutations = et_permutations.
61ENDIF.
62ENDDO.
63
64ENDFUNCTION.
Algorithm description viewbox

ABAP Advanced String Permutation Generation

Algorithm description:

This ABAP program generates all unique permutations of a given input string. It employs a recursive approach with backtracking. A key feature is its ability to handle strings with duplicate characters by using a set at each recursion level to track characters already considered, thus preventing redundant permutation generation. This is useful in scenarios like generating unique password combinations or exploring all possible arrangements of elements in a sequence.

Algorithm explanation:

The algorithm uses a depth-first search (DFS) strategy implemented recursively to explore all possible arrangements of characters. The `generate_permutations_recursive` function takes the current permutation being built and the remaining characters as input. The base case is when no characters are left, at which point the complete permutation is added to the result table. For the recursive step, it iterates through the remaining characters. To handle duplicates, it maintains a local set (`lo_used_chars`) to ensure that each character is used only once at a specific position within a given recursive call. This prevents generating identical permutations when the input string has repeated characters. The time complexity is roughly O(N! * N) in the worst case for strings with unique characters, where N is the length of the string, due to the factorial nature of permutations and string manipulations. For strings with duplicates, it's more efficient but still grows rapidly. The space complexity is O(N) for the recursion depth and string storage.

Pseudocode:

FUNCTION generate_permutations(input_string):
  result_permutations = empty list
  CALL recursive_helper(current_permutation = "", remaining_chars = input_string, result = result_permutations)
  RETURN result_permutations

FUNCTION recursive_helper(current_permutation, remaining_chars, result):
  IF remaining_chars is empty:
    ADD current_permutation to result
    RETURN

  used_chars_at_level = empty set
  FOR EACH character `char` in remaining_chars:
    IF `char` is NOT in used_chars_at_level:
      ADD `char` to used_chars_at_level
      new_permutation = current_permutation + `char`
      new_remaining = remaining_chars with `char` removed
      CALL recursive_helper(new_permutation, new_remaining, result)