For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst case than the following algorithm:
def algo_X(A):
i = 0
j = len(A)-1
while i < j:
if A[i] != A[j]:
k = i + 1
while k < j:
if A[i] == A[k]:
A[k], A[j] = A[j], A[k]
break
elif A[j] == A[k]:
A[k], A[i] = A[i], A[k]
break
else:
k += 1
if k == j:
return False
i += 1
j -= 1
return True
This algorithm returns True if the elements of list passed as argument can be manipulated (swapped) in order to create a new list, which, if we read from the left or from the right, has the same order of elements (palindrome). Else returns False.
For example, this list ['a', 'a', 'b', '2', 'b', 'b', ‘2’] can be ordered so that we have a list with the same elements in the same positions, if we read at the same time from the left and from the right: ['a', 'b', '2', 'b', '2', 'b', ‘a’].
Note that this is my interpretation of the algorithm, they did not tell us what this algorithm was supposed to do.
If I am not wrong, this algorithm, in the worst case (and average case), is O(n2), and Ɵ(n) in the best case.
The exercise specifically states that I don’t have necessarily to change the list (like in algo_X), but just to return True or False specifying respectively if the list can be made a palindrome or not.
We cannot use libraries, but just built-in constructs. We cannot even use slice, for example. This is because we don’t “know” exactly the time complexity of those functions. I will edit my question
To make a better algorithm for the worst case, I thought I could use merge sort, whose time complexity is always n*log(n), plus a loop, which would not make the algorithm worse, asymptotically.
This is my merge function for my merge sort function:
def merge(A, B):
ls = []
a, b = 0, 0
while a < len(A) and b < len(B):
if A[a] <= B[b]:
ls.append(A[a])
a += 1
else:
ls.append(B[b])
b += 1
while a < len(A):
ls.append(A[a])
a += 1
while b < len(B):
ls.append(B[b])
b += 1
return ls
This is my merge sort function:
def merge_sort(A):
if len(A) < 2: # basic condition
return A
L = merge_sort(A[0:len(A)//2])
R = merge_sort(A[len(A)//2:])
return merge(L, R)
Finally, here’s my alternative, which returns True, if the list can be made a palindrome, False otherwise:
def better_algo_x(A):
if len(A) < 2:
return True
sorted_A = merge_sort(A)
odd_groups = 0
current = sorted_A[0]
c = 1 # Used to count the number of characters that are equal between them
for i in range(1, len(sorted_A)):
if current == sorted_A[i]:
c += 1
else:
if c % 2 == 1:
odd_groups += 1
if odd_groups > 1:
return False
current = sorted_A[i]
c = 1
# for the last group of characters
if c % 2 == 1:
odd_groups += 1
if odd_groups > 1:
return False
return True
I have a few questions:
-
Are my functions correct?
-
Is my analysis of the time complexity of the algorithm
algo_Xcorrect? -
Does my
better_algo_xdo what it is supposed to do? -
Does it do it in n*log(n) in the worst case?
-
Can I still improve it? How?
-
Do you know (other) better alternatives for
algo_X?
Of course, some questions might seem silly, but I would like to hear the opinion of some experts. Of course, I have tried my algorithms.
0
Yes, your analysis and algorithms are correct. But it can be made better by trading off memory for performance IF the amount of possible characters in string is limited (eg. it is not full Unicode). Basically, you can use hash-map to keep count of every character in O(n)*O(1) and then go through the list in O(1) (because the count of all possible characters is always the same). Meaning O(n)*O(1)+O(1) = O(n) in worst case.
def isPalindromic(A):
hashArray = array.array('I', [0] * 256)
for ch in A:
ascii = ord(ch)
hashArray[ascii] += 1
notEven = 0
for count in hashArray:
if (count > 0 and count % 2 == 1):
notEven += 1
return notEven <= 1 #one can be even, then it will be in the center
1
Starting from the answer from Euphoric, no reason to restrict your character pool:
from collections import defaultdict
def isPalindromic(A):
counter = defaultdict(int);
# initializes a dictionary that returns 0 if the key is missing
for letter in A:
counter[letter] += 1
notEven = len([count for count in counter.values() if count % 2 == 1])
# if you want to avoid the extra list allocation,
# this is less clear but more efficient:
notEven = sum(1 for count in counter.values() if count % 2 == 1)
return notEven <= 1
For reasoning about the complexity, note that:
- You iterate once over the entire array to count the letters and insertion in the dictionary is constant time (
O(n)) - You iterate over all the values of the dictionary, the values are at most
n, soO(n)
In particular, the complexity is O(n) with an additional space complexity of O(n) (worst case scenario, the array has all distinct values).
2