Generating all the sub-arrays of an array

gravatar
By Ranti
 · 
February 10, 2023
 · 
2 min read

Pre-requisite knowledge

  • Arrays

Arrays are fundamental data structures in computer science, providing a convenient way to store and manipulate collections of elements.

A sub-array is any contiguous block of an array. A contiguous block in the array must have at least one element. You cannot change the order of the elements in the array.

Naive Approach

The most straightforward approach to generating sub-arrays is to use nested loops. The outer loop will iterate over the starting index, and the inner loop will iterate over the ending index. For each pair of indices, the sub-array can be extracted. While this method is simple, it is not the most efficient.

def generate_sub_arrays(arr):
    sub_arrays = []
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            sub_arrays.append(arr[i:j+1])
    return sub_arrays
Python

Recursive Approach

A more elegant and efficient way to generate sub-arrays is by using recursion. This approach involves dividing the problem into smaller sub-problems. To generate sub-arrays, we can recursively explore the sub-arrays that start at different positions and have different lengths.

def generate_sub_arrays_recursive(arr):
    if len(arr) == 0:
        return [[]]
    sub_arrays = generate_sub_arrays_recursive(arr[:-1])
    return sub_arrays + [x + [arr[-1]] for x in sub_arrays]
Python

Bitmasking Approach

Another efficient technique involves using bit manipulation to generate sub-arrays. This approach uses a bitmask to represent whether an element is included or excluded from a sub-array. By iterating through all possible bitmasks, we can generate all sub-arrays.

def generate_sub_arrays_bitmask(arr):
    n = len(arr)
    sub_arrays = []
    for i in range(1 << n):
        sub_array = [arr[j] for j in range(n) if (i & (1 << j)) != 0]
        sub_arrays.append(sub_array)
    return sub_arrays
Python

Time and Space Complexity

  • Naive Approach: O(n3) time complexity due to the nested loops.
  • Recursive Approach: O(2n) time complexity, as it generates all possible combinations of elements.
  • Bitmasking Approach: O(2n • n) time complexity, where n is the length of the array.

In terms of space complexity, all three approaches have O(2n • m) space complexity, where n is the length of the array and m is the average size of sub-arrays.

Conclusion

Generating sub-arrays is a common operation in array manipulation. Depending on the size of the array and the specific requirements of your application, different approaches may be more suitable. The recursive approach is elegant and efficient, while the bitmasking approach offers a balance between efficiency and simplicity. The naive approach, although straightforward, is not the most efficient for large arrays.

View