uday
BAN USERRun time: O(n)
Assumptions:
1) Input is sorted
Python:
def no_repeat(inp, flip_side=False):
i = 0
while i < len(inp) - 1:
if inp[i] == inp[i+1]:
if inp[i] == inp[-1]:
if flip_side:
return False
else:
rev_inp = list(inp)
rev_inp.reverse()
return no_repeat("".join(rev_inp), True)
else:
inp = inp[:i+1] + inp[-1] + inp[i+1:-1]
i+=1
return inp
My solution is similar to koosha.nejad's
Dynamically generate:
1. count from 1 to m^n
2. convert index to base-m
3. convert each digit into index into element set
4. construct next value
def convert_to_base(num, base):
digits = []
while num > 0:
digits.append(num % base)
num = num / base
digits.reverse()
return digits
def set_permute(element_set, n):
for i in xrange(0, len(element_set)**n): # Step 1.
digits = convert_to_base(i, len(element_set)) #Step 2.
for k in range(0, n - len(digits)): #Step 3.
digits.insert(0, 0)
next_element = [element_set[digit] for digit in digits] #Step 4.
yield next_element
Analysis:
Memory usage virtually eliminated, though convert_to_base is more computationally intensive. However, this a
lgorithm is embarrassingly parallelizable.
Does this work for 'abccc'?
- uday November 01, 2015