"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
Top comments (0)