## DEV Community is a community of 753,853 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Scott Gordon

Posted on

# 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