## Anagrams, Again

### October 18, 2019

We first check the two strings are the same length. Then we count characters in 256 buckets, adding 1 for each character in the first string and adding -1 for each character in the second string. Finally, we scan the 256 buckets and report an anagram if and only if all buckets have a 0 value:

```(define (anagram? str1 str2)
(if (not (= (string-length str1) (string-length str2))) #f
(let ((buckets (make-vector 256 0)))
(do ((cs (string->list str1) (cdr cs))) ((null? cs))
(let ((i (char->integer (car cs))))
(vector-set! buckets i (+ (vector-ref buckets i) 1))))
(do ((cs (string->list str2) (cdr cs))) ((null? cs))
(let ((i (char->integer (car cs))))
(vector-set! buckets i (- (vector-ref buckets i) 1))))
(let loop ((i 0))
(if (= i 256) #t
(if (not (zero? (vector-ref buckets i))) #f
(loop (+ i 1))))))))```

Here’s an example:

```> (anagram? "time" "emit")
#t```

You can run the program at https://ideone.com/qTqySy.

Pages: 1 2

### 8 Responses to “Anagrams, Again”

1. Paul said

In Python. These functions work for ascii and for unicode.

```from collections import Counter

def is_anagram(a, b):
return sorted(a) == sorted(b)

def is_anagram(a, b):
return Counter(a) == Counter(b)
```
2. Zack said

Here is my take on this, using Julia 1.1.1, without any dependencies: https://pastebin.com/9LgUHJr8

Have a nice weekend!

3. Daniel said

Here’s a solution in C.

```#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

bool check_anagrams(char* s1, char* s2) {
int diff = {0};
for (char* s = s1; *s != '\0'; ++s) {
++(diff[(unsigned char)(*s)]);
}
for (char* s = s2; *s != '\0'; ++s) {
--(diff[(unsigned char)(*s)]);
}
for (int i = 0; i < 256; ++i) {
if (diff[i]) return false;
}
return true;
}

int main(int argc, char* argv[]) {
if (argc != 3) return EXIT_FAILURE;
bool anagram = check_anagrams(argv, argv);
printf("%d\n", anagram);
return EXIT_SUCCESS;
}
```

Example:

```\$ ./a.out programming praxis
0

\$ ./a.out praxis xsairp
1
```
4. Daniel said

Here’s a sorting-based solution in C.

```#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
char a_ = *((char*)a);
char b_ = *((char*)b);
return (a_ > b_) - (a_ < b_);
}

// destructive
bool check_anagrams(char* s1, char* s2) {
qsort(s1, strlen(s1), 1, compare);
qsort(s2, strlen(s2), 1, compare);
return strcmp(s1, s2) == 0;
}

int main(int argc, char* argv[]) {
if (argc != 3) return EXIT_FAILURE;
bool anagram = check_anagrams(argv, argv);
printf("%d\n", anagram);
return EXIT_SUCCESS;
}
```

Example:

```\$ ./a.out programming praxis
0

\$ ./a.out praxis xsairp
1
```
5. matthew said

@Paul: you need to be a bit careful with this approach with Unicode. Here’s an attempt to deal with combining characters, equivalences & casing:

```import unicodedata

def signature(s):
# Apply compatibility decomposition
s = unicodedata.normalize('NFKD',s)
# Include: Letter, Number, Symbol.
# Exclude: Mark, Punctuation, Separator, Other
s = [c.lower() for c in s if unicodedata.category(c) in "LNS"]
s = "".join(sorted(s))
return(s)

print(sorted("Ångström") == sorted("Ångström"))  # => False
print(signature("Ångström") == signature("Ångström")) # => True
print(signature("Ångström")) # => agmnorst
print(signature("Ἀχιλλεύς")) # => αειλλςυχ
print(signature("H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝S̨̥̫͎̭ͯ̿̔̀ͅ")) # => ceehmos
```
6. matthew said

I’m a bit disappointed that Chrome on my Android phone can’t cope with the combining characters in that last post at all, FF on Linux seems to manage though.

7. matthew said

Just trying something: “Ångström”, “Ἀχιλλεύς”, “H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝S̨̥̫͎̭ͯ̿̔̀ͅ”

8. matthew said

OK, Chrome on Android just seems to have problems when displaying with its code font.