אנגרמות

בהינתן מערך של מחרוזות, המשימה היא להחזיר את כל קבוצות המחרוזות שהם אנגרמות אחת של השנייה.
אנגרמה היא מחרוזת שמורכבת מאותן אותיות של מחרוזת אחרת, בסדר שונה.

הדוגמא שנתונה לנו בשאלה היא זו – 

arr = [“cat”, “dog”, “god”, “tca”] find_anagrams(arr) = [[1, 4], [2, 3]]

שתי השאלות שישר צצות לי כשאני רואה את המשימה הזו הן –

1. האם מחרוזת יחידה יכול להיחשב לקבוצת אנגרמות בגודל 1?
2. האם יכולות להיות לי במערך שתי מחרוזות זהות, ובמקרה כזה האם הן נחשבות לקבוצה?

אז שאלתי את ה”מראיין” שלי (האתר ממנו לקחתי את השאלה) והתשובה לשתי השאלות שלי היא כן.
אני אכתוב עוד כמה דוגמאות קטנות שמשקפות את מקרי הקצה האלה –

arr = [“cat”] find_anagrams(arr) = [[1]] arr = [“dog”, “god”, “dog”] find_anagrams(arr) = [[1, 2, 3]]

כרגיל, אני אתחיל מהפתרון הנאיבי.
הפתרון הנאיבי פה הוא די גנרי – לולאה בתוך לולאה שעבור כל מחרוזת במערך תעבור על כל שאר המחרוזות ותבדוק אם הן אנגרמות של המחרוזת הראשונה.
אני אכתוב את הפתרון הזה במהירות – 

def find_anagrams(arr):
	results = []
	for i in range(0,len(arr)):
		word = arr[i]
		current_result = [i+1]
		for j in range(i+1, len(arr)):
			if is_anagram(word, arr[j]):
				current_result.append(j+1)
		results.append(current_result)
	return results

עכשיו שאני מסתכלת על הקוד אני כבר רואה בעיה בפתרון הנאיבי שלי – אני אריץ דוגמא שמדגימה טוב את הבעיה.

find_anagrams([“dog”, “god”, “odg”]): results = [] i=0 word = “dog” current_result = [1] j=1 is_anagram(dog, god) == True → current_result = [1,2] j=2 is_anagram(dog, odg) == True → current_result = [1,2, 3] results = [[1,2, 3]] i=1 word = “god” current_result = [2] j=2 is_anagram(god, odg) == True → current_result = [2,3] results = [[1,2, 3], [2,3]]

הבעיה היא שאני עוברת על אותן מחרוזות יותר מפעם אחת, ועושה את אותן השוואות יותר מפעם אחת – גם לא יעיל, וגם נותן תוצאה לא נכונה בסוף.

כדי לתקן את הפתרון שלי אני יכולה להשתמש במערך עזר שיכיל את כל המחרוזות שעדיין לא מצאתי להן אנגרמה וכל פעם להתחיל את החיפוש מחדש על המחרוזות שנותרו במערך, סוג השימוש הזה מזכיר לי שימוש נפוץ של תור – אני כל פעם אוציא מחרוזת אחת מהתור, ואחפש את האנגרמות שלה, כל האנגרמות שמצאתי יצאו מהתור, וכן הלאה עד שהתור יתרוקן.

אני אכתוב את הפתרון הזה – 

def find_anagrams(arr):
	results = []
	str_queue = {}
	for i in range(0, len(arr)):
		str_queue[arr[i]] = i+1
	while len(str_queue) > 0:
		word, i = str_queue.popitem()
		current_result = [i]
		while len(str_queue) > 0:
		second_word, j = str_queue.popitem()
			if is_anagram(word, second_word):
				current_result.append(j)
			else:
				str_queue[second_word] = j
		results.append(current_result)
	return results

כבר נראה יותר טוב.

ההעתקה הראשונית של כל האיברים מהמערך לתור יכולה להיראות קצת בזבזנית, אך היא נעשית ב-(O(N, שהוא גם כך חסם תחתון לאלגוריתם שצריך לעבור על כל המילים במערך, אז זה לא מדאיג אותי.
אני אריץ דוגמא עם האלגוריתם החדש שלי –

find_anagrams([“dog”, “god”, “odg”]): results = [] str_queue = {“dog”:1, “god”: 2, “odg”: 3} word = dog, i=1 str_queue = {“god”: 2, “odg”: 3} current_result = [1] second_word = “god”, j=2 str_queue = {“odg”: 3} is_anagram(dog, god) == True → current_result = [1,2] second_word = “odg”, j=3 is_anagram(dog, odg) == True → current_result = [1,2, 3] results = [[1,2,3]] return [[1,2,3]]

מגניב, הדוגמא הזו נראית טוב.

אני לא כל כך אוהבת את זה שאני מכניסה ומוציאה דברים מהתור במקום לעשות peek, אבל כיוון שאין פונקציונליות כזו בפייתון, זה הפתרון הכי מהיר כרגע (בקוד אני אכתוב מעטפת).

עכשיו, מה הסיבוכיות של הפתרון הזה?
יש לי כאן לולאה בתוך לולאה. במקרה הטוב התור יתרוקן תוך כדי עבודה, אבל במקרה הגרוע (נגיד המקרה שבו אף מילה במערך היא לא אנגרמה של מילה אחרת) הסיבוכיות שלי תהיה (O(N².

האם אני יכולה לשפר את הפתרון הזה? בהחלט!

מה בעצם המשמעות של אנגרמות? אם שתי מילים הן אנגרמה אחת של השנייה אז הן מכילות את אותן אותיות בסדר שונה. כלומר, אם נמיין כל אחת מהמילים התוצאה תהיה זהה – אני יכולה להשתמש בתכונה הזו.

אם אני אשתמש בטבלה, שבה אני מרכזת את כל המילים שהמיון שלהן נותן תוצאה זהה יחד, אני אוכל לקבל את החלוקה לקבוצות של אנגרמות ב-(O(N.
אני אכתוב את הפתרון הזה – 

def find_anagrams(arr):
	results = defaultdict(list)
	for i in range(0,len(arr)):
		word = arr[i]
		word_key = ‘,’.join(sorted(word))
		results[word_key].append(i+1)
	return results.values()

מגניב, יעיל ואלגנטי.
אני אריץ את הדוגמא על הפתרון הזה – 

find_anagrams([“dog”, “god”, “odg”]): results = {} i=0 word = “dog” word_key = “dgo” results = {“dgo”: [1]} i=1 word = “god” word_key = “dgo” results = {“dgo”: [1, 2]} i=2 word = “odg” word_key = “dgo” results = {“dgo”: [1, 2, 3]} return [[1,2,3]]

וואו, מהמם.
אני יכולה לראות שגם הדומא של איברים שהם יחידים בקבוצה תעבוד, וגם הדוגמא של שתי מילים זהות. ואפילו המקרה של מערך ריק יעבוד פה.

הידד!!

מה הסיבוכיות של האלגוריתם? אני עוברת על כל מילה במערך פעם אחת, ועושה עליה פעול מיון. המחיר של פעולת מיון על מילה באורך K היא (O(KlogK. כלומר, הסיבוכיות המלאה של האלגוריתם היא (O(NKlogK.
בדוגמא שנתתי פה זה די זניח, אבל קל לי לתאר לעצמי מקרה שבו יש לי מערך עם שלוש מילים, כל אחת באורך מיליון, ואז הפקטור המשמעותי בסיבוכיות הופך להיות פעולת המיון, ואז האלגוריתם שלי הוא כבר לא לינארי.

האם אני יכולה לשפר עוד את הפתרון שלי? כן!
במקום למיין את המילים – אני יכולה לספור את התדירות של האותיות. כמו במקרה של מיון, התדירות של כל אות במילה היא תכונה שנשמרת באנגרמות ולכן יכולה לספק לנו מפתח.
אני אכניס את התיקון הזה לאלגוריתם שלי – 

def get_word_key(word):
	hist = defaultdict(int)
	for c in word:
		hist[c] += 1
	str_hist = [“%s%d” % item for item in hist.items()]
	return ‘’.join(str_hist)

def find_anagrams(arr):
	results = defaultdict(list)
	for i in range(0,len(arr)):
		word = arr[i]
		word_key = get_word_key(word)
		results[word_key].append(i+1)
	return results.values()

מגניב, אני אריץ שוב את הדוגמא – 

find_anagrams([“dog”, “god”, “odg”]): results = {} i=0 word = “dog” word_key = “d1o1g1” results = {“d1o1g1”: [1]} i=1 word = “god” word_key = “g1o1d1”

אופס, באג.
הפונקציה items לא ממיינת איברים, היא מחזירה אותם על פי סדר הכנסתם. אם אני רוצה את האיברים ממוינים (כדי שכל האנגרמות יחזירו את אותו המפתח) אני צריכה לחשוב איך להשיג את זה.

אני יכולה להחזיק מילון ממוין או למיין את התוצאות. כיוון שהמקסימום של אותיות שונות שיכולות להיות לי הוא 52 (כל האותיות באנגלית, lowercase או uppercase), אני יודעת שהסיבוכיות תהיה קבועה – 52Log52.
פתרון נוסף הוא לעבור בלולאה על כל האותיות האפשריות ולמצוא את התדירות שלהן. הסיבוכיות של הפתרון הזה היא לינארית בגודל 52.
במקרה הנוכחי, כיוון שהגודל שלנו חסום וידוע באמת מדובר בשני פתרונות שקולים ולא משנה באיזה מהם אני אבחר.
אני אתקן את האלגוריתם בהתאם – 

def get_word_key(word):
	hist = defaultdict(int)
	for c in word:
		hist[c] += 1
	str_hist = ""
	for c in string.ascii_letters:
   		str_hist += "%s%d" % (c, hist[c])

	return ‘’.join(str_hist)

הסיבוכיות של הפונקציה החדשה שלי get_word_key היא (O(K (כיוון שהסיבוכיות של המעבר על כל האותיות היא קבועה), והסיבוכיות הכוללת של האלגוריתם היא (O(NK. מעולה.

עכשיו, לפני שאני הולכת לכתוב קוד הערה קטנה – במקרה הזה הפתרון היעיל שהגעתי אליו הוא הרבה יותר קצר ופשוט מהפתרון הנאיבי, ואם הייתי בראיון אמתי כנראה שהייתי מציינת את הרעיון פתרון הנאיבי שלי ושואלת את המראיין אם אני יכולה להמשיך הלאה בלי לממש אותו. בפוסט הזה רציתי ממש לקחת את הזמן לפרט את הפתרון הנאיבי שלי, לרשום את התיקון שלו ולראות למה הוא פחות טוב מהפתרון היעיל.

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/anagrams.py