Permutations

"Given a set of distinct numbers, find all of its permutations."

Just recently I got stuck on this problem and ended up using a brute force technique that was not only inefficient, did not entirely solve the problem.

I found at least two ways to solve this properly (Grokking the Coding Interview: Patterns for Coding Questions .. (n.d.) One way is far superior based on time complexity. Let's begin with the less efficient pattern first:

Subsets Pattern with Time Complexity of O(N*N!)

# subsets_str_perm.py
#   Given a set of distinct letters, find all of its permutations.
# by: Scott Gordon

from collections import deque


def get_permutation(string):
    string_length = len(string)
    result = []
    permutations = deque()
    permutations.append([])
    for current_letter in string:
        # Take all permutations and add current num to make new permutation
        s = len(permutations)
        for _ in range(s):
            old_permutation = permutations.popleft()
            # Create new permutation by adding current num @ every position
            for j in range(len(old_permutation) + 1):
                new_permutation = list(old_permutation)
                new_permutation.insert(j, current_letter)
                if len(new_permutation) == string_length:
                    result.append(new_permutation)
                else:
                    permutations.append(new_permutation)

    return result


def find_permutation(string, pattern):
    permuted_pattern = get_permutation(pattern)
    for substring in permuted_pattern:
        s = "".join(substring)
        if s in string:
            result = True
            break
        else:
            result = False
    return result


def main():
    print("Permutation exist: " + str(find_permutation("oidbcaf", "abc")))
    print("Permutation exist: " + str(find_permutation("odicf", "dc")))
    print("Permutation exist: " + str(find_permutation("bcdxabcdy", "bcdyabcdx")))
    print("Permutation exist: " + str(find_permutation("aaacb", "abc")))


main()

Next let's take a look at the more efficient pattern:

Sliding Window Pattern with Time Complexity of O(N)

# sliding_win_str_perm.py
#    Given a set of distinct numbers, find all of its permutations
# by: Scott Gordon


def find_permutation(str1, pattern):
    window_start, matched = 0, 0
    char_frequency = {}
    # Create a HashMap to calculate frequencies of all chars in pattern.
    for chr in pattern:
        if chr not in char_frequency:
            char_frequency[chr] = 0
        char_frequency[chr] += 1

    # Iterate through string, add one char at a time to sliding window.
    for window_end in range(len(str1)):
        right_char = str1[window_end]
        if right_char in char_frequency:
            # If added char matches HashMap char, decrement map frequency. If
            # char frequency zero, complete match.
            char_frequency[right_char] -= 1
            if char_frequency[right_char] == 0:
                matched += 1

        # If num of char matched equal to num of distinct chars in
        # pattern (total chars in HashMap), required permutation
        # achieved.
        if matched == len(char_frequency):
            return True

        # If win size > len of pattern, shrink win to make == pattern size.
        # If outgoing char part of pattern, put back in frequency HashMap.
        if window_end >= len(pattern) - 1:
            left_char = str1[window_start]
            window_start += 1
            if left_char in char_frequency:
                if char_frequency[left_char] == 0:
                    matched -= 1
                char_frequency[left_char] += 1

    return False


def main():
    print("Permutation exist: " + str(find_permutation("oidbcaf", "abc")))
    print("Permutation exist: " + str(find_permutation("odicf", "dc")))
    print("Permutation exist: " + str(find_permutation("bcdxabcdy", "bcdyabcdx")))
    print("Permutation exist: " + str(find_permutation("aaacb", "abc")))


main()

So, I went from brute forcing the algorithm in my original context, to solving the problem using the subsets pattern, then to improve upon its time complexity using the sliding window pattern. I would recommend running these patterns and debugging them over and over again if this is challenging, I know I had to.

References:

Grokking the Coding Interview: Patterns for Coding Questions .. (n.d.). www.educative.Io. Retrieved October 3, 2021, from https://www.educative.io/courses/grokking-the-coding-interview

Photo by Jean-Louis Paulin on Unsplash