"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)