Substring Subset Permutation Combination


# O(n^3)
import itertools

def substring(s):
substrings = []
for i in range(len(s)):
for j in range(i + 1, len(s)+1):
substrings.append(s[i:j])
return substrings

# O(2^N)
def subset(s):
store = []
running = []
def helper(s, index, running, store):
if index == len(s):
store.append("".join(running))
return
running.append(s[index])
helper(s, index + 1, running, store)
running.pop()
helper(s, index + 1, running, store)
helper(s, 0, running, store)
return store

# O(N!)
def permutation(s):
#print(s)
if len(s) == 1:
return [s]
base = s[0]
array = permutation(s[1:])
newarray = []
for word in array:
for i in range(len(word)+1):
addedword = word[:i] + base + word[i:]
newarray.append(addedword)
#print(newarray)
return newarray

# O(N!)
def combination(s, r):
visited = set()
running, store = [], []
def helper(s, index, r, visited, running, store):
if len(running) == r:
store.append("".join(running))
return
if len(s) == index:
return
for i in range(index, len(s)):
if i not in visited:
running.append(s[i])
visited.add(i)
helper(s, index + 1, r, visited, running, store)
running.pop()
visited.discard(i)
helper(s, 0, r, visited, running, store)
return store

s = "abc"
#s = "stackover"
print(substring(s))
print(subset(s))
print(combination(s, 3))
print(combination(s, 2))
print(combination(s, 1))
print(permutation(s))

print("PYHTON itertools library ")
import itertools
import math

print("PERMUTATION For array :3P3")
print(math.factorial(3))
print(list(itertools.permutations([1,2,3])))

print("PERMUTATION [1,2,3], 2 :3P2")
print(math.factorial(3)//math.factorial(3-2))
print(list(itertools.permutations([1,2,3],2)))

print("PERMUTATION [1,2,3], 1 : 3P1")
print(math.factorial(3)//math.factorial(3-1))
print(list(itertools.permutations([1,2,3],1)))

print("COMBINATION [1,2,3], 3 : 3C3")
print(math.factorial(3)//(math.factorial(3-3)*math.factorial(3)))
print(list(itertools.combinations([1,2,3], 3)))

print("COMBINATION [1,2,3], 2 : 3C2")
print(math.factorial(3)//(math.factorial(3-2)*math.factorial(2)))
print(list(itertools.combinations([1,2,3],2)))

print("COMBINATION [1,2,3], 1 : 3C1")
print(math.factorial(3)//(math.factorial(3-1)*math.factorial(1)))
print(list(itertools.combinations([1,2,3],1)))


def nPr(n, r):
return int(math.factorial(n)//math.factorial(n-r))

def nCr(n, r):
return int(math.factorial(n)/(math.factorial(n-r)*math.factorial(r)))