## Anagrams Within Words

### February 21, 2014

Our algorithm slides a window the length of the search string along the target string, at each step comparing a frequency count of the letters in the window with a frequency count of the letters in the search string. As the window slides along the target string, the frequency count is updated by removing the farthest-back letter from the current count and adding the new letter to the count:

```(define (anagram-in-word needle haystack)   (let* ((len (string-length needle))          (stop (string-length haystack))          (needle (sort charlist needle)))          (window (sort charlist haystack)))))     (let loop ((lo 0) (hi (- len 1)) (window window))       (cond ((= hi stop) #f)             ((equal? needle window) #t)             (else (loop (+ lo 1) (+ hi 1)                         (insert (string-ref haystack hi)                           (remove (string-ref haystack lo)                             window))))))))```

The frequency count is stored as a list of characters in alphabetical order, without counts; we use Scheme’s `equal?` predicate to determine if two lists are the same. Here are the two auxiliary functions:

```(define (remove x xs) ; delete first occurrence of x in xs   (call-with-values     (lambda () (split-while (lambda (c) (char<? c x)) xs))     (lambda (front back) (append front (cdr back)))))```

```(define (insert x xs) ; insert x in order in xs   (call-with-values     (lambda () (split-while (lambda (c) (char<? c x)) xs))     (lambda (front back) (append front (list x) back))))```

Here are the two examples:

```> (anagram-in-word "cat" "actor") #t > (anagram-in-word "car" "actor") #f```

We used `take` and `split-while` from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/JJ0UVuws.

Pages: 1 2

### 13 Responses to “Anagrams Within Words”

1. some posiblidades were missing, the ideal thing would be with a ringlet but I feel sleepy and want to sleep, greetings

def check_anagr(anagram, string):
lib = {}
string = str(string)
for x in range(3):
lib[x] = string[x:x+1]
posibilidades = [‘110’, ‘100’, ‘000’, ‘001’, ‘011’, ‘111’, ‘220’,’200′, ‘222’,’211′, ‘112’, ‘002’,’022′, ‘020’, ‘012’, ‘112’, ‘021’, ‘212’, ‘221’, ‘121’, ‘120’, ‘102’]
r = i
var = ‘{}{}{}’.format(lib[int(r[0])], lib[int(r[1])], lib[int(r[2])])
if anagram == var:
return True
else:
return False

>>> check_anagr(‘cat’, ‘actor’)
True
>>> check_anagr(‘car’, ‘actor’)
False
>>>

2. Paul said

In Python.

```from collections import Counter
from itertools import islice, tee, izip

def update(counter, a, b):
'replace a by b in Counter'
counter[b] += 1
counter[a] -= 1
if counter[a] == 0:
del counter[a]

def anagram(first, second):
ita, itb = tee(iter(second))
target = Counter(first)
actual = Counter(islice(itb, len(first)))
if target == actual:
return True
for a, b in izip(ita, itb):
update(actual, a, b)
if target == actual:
return True
return False

print anagram("trel", "appletree") # True
print anagram("reel", "appletree") # False
print anagram("diep", "parallellepipedum") # True
print anagram("dier", "parallellepipedum") # False
```

/* function prototypes */
bool searchForChar(char c, char* small_word);
bool isAnagram(char* small_word, char* large_word);

/* function definitions */
int main(void)
{
char* small_word;
char* large_word; // set variable for the 2 words

printf(“Small word is: “); // ask for the small one
scanf(“%s”, small_word);

printf(“Large word is: “); // ask for the large one
scanf(“%s”, large_word);

char* result;

if (isAnagram(small_word, large_word)) result = “match!”; // check and print the result
else result = “no matching!”;

printf(“%s\n”, result);
}

/* for example, we have “cat” and “actor”.
we are going to divide “actor” into triplets like that (act, cto, tor)
then we will test matching between each triplet and the small word
if matching present our function will return (true) */

bool isAnagram(char* small_word, char* large_word)
{
int len_of_small = strlen(small_word); // get the length of the small word

int len_of_large = strlen(large_word); // get the length of the large one

int counter; // set a counter to check full matching

for (int i = 0; i <= len_of_large – len_of_small; i++) // iterate over the large word till the index before the end by the length of the small one
{
counter = 0; // set the counter at zero

for (int j = i; j < i + len_of_small; j++) // iterate over the large word from the current index (i) for the length of the small
{
if(searchForChar(large_word[j], small_word)) counter++; // check if the current char is present in the small word and if so update counter
}

if (counter == len_of_small ) return true; // if counter reach the length of the small word return true
}

return false; // else, return false
}

bool searchForChar(char c, char* small_word)
{
for (int i = 0, len = strlen(small_word); i < len; i++) // iterate over the small word and see if the char sent from prev. function exists in it
{
if (small_word[i] == c)
{
return true; // if so, return true
}
}

return false; // else, return false
}

4. GyrosOfWar said

Lazy solution in Clojure using math.combinatorics/permutations:
http://pastebin.com/NHwcLt4M

5. PHP Solution: http://pastebin.com/1mur1TUs

/anagram.php
Enter anagram: cat
Enter word: actor
bool(true)

./anagram.php
Enter anagram: car
Enter word: actor
bool(false)

./anagram.php
Enter anagram: top
Enter word: boptin
bool(true)

./anagram.php
Enter anagram: butt
Enter word: tubtin
bool(true)

6. Toxic said

In Java code:

public static boolean testAnagram(String originalWord, String containedWord)
{
char [] first = originalWord.toCharArray();//Get the first word and store it into a character array.
char [] second = containedWord.toCharArray();//Get the second word and store it into a character array.
int [] index = new int[second.length];//An int array that stores the index of matching letters contained in the original array.
int counter = 0;//Keep count of the index storage position.

//Compare each character of both words.

for(int i = 0; i < second.length; i++)
{
for(int j = 0; j < first.length; j++)
{
if(second[i] == first[j])
{
index[counter] = j; //Store matching letters.
counter++; //Increment the index storage position.
break;//Break for loop.
}
}
}

if(counter < second.length)return false;//If not all letters were found.

//get the distance between the indices which should be no more than one
//less than the contained word length (to qualify as an anagram)

for(int i = 0; i < index.length; i++)
{
for(int j = 0; j = second.length) return false;
}
}

//If all qualifications are met.
return true;
}

7. vibhumishra007 said

hello Friends
Solution in c—->

#include
#include
#include
#include
char arr1[4];
int flag=0;
void swap(char*,char*);
void permut(char*,int ,int);
void swap(char *x,char *y)
{
char temp;
temp=*x;
*x=*y;
*y=temp;
}
void permut(char *a,int i,int n)
{
int j;
if(i==n)
{
char *ptr=NULL;
ptr=strstr(a,arr1);
if(ptr!=NULL)
{
printf(“true”);
flag=1;
getch();
exit(0);
}
}
else
{
for(j=i;j<=n;j++)
{
swap((a+i),(a+j));
permut(a,i+1,n);
swap((a+i),(a+j));//backtarck
}
}
}

void main()
{
strcpy(arr1,"cea");
char arr[]="actor";
clrscr();
permut(arr,0,4);
if(flag==0)
printf("false");
getch();
}

8. […] implemented the Anagrams Within Words programming puzzle from Programming Praxis in Python, a language I haven’t used since my […]

9. matthew said

A late entry here in C++: use a multiset (possibly with negative element counts) to store the difference between target characters and the characters in the string being searched. Incrementally keep track of the size of the difference and output the string offset if difference is zero.

```#include <stdio.h>
#include <string.h>
#include <assert.h>

template <typename Element, int N>
class MSet {
public:
MSet() : elems(), sz(0) {}
if (++elems[c] > 0) sz++;
else sz--;
}
void sub(Element c) {
if (--elems[c] < 0) sz++;
else sz--;
}
int size() const { return sz; }
private:
int elems[N];
int sz;
};

void check (const char *s, const char *t)
{
int slen = strlen(s);
int tlen = strlen(t);
assert(slen <= tlen);
printf("'%s' '%s':",s,t);
MSet<unsigned char, 256> mset;
for(int i = 0; i < slen; i++) {
}
if (mset.size() == 0) printf(" %d", 0);
for(int i = slen; i < tlen; i++) {
if (mset.size() == 0) printf(" %d", i-slen+1);
}
printf("\n");
}

int main()
{
check("","");
check("","foo");
check("foo","foooof");
check("foo","foofoo");
check("bar","foobaz");
check("foo","barfoo");
check("foo","foo foo");
check("fff","fffffff");
}
```
10. A not so efficient solution in Python:

```import itertools

def anagram(a, b):
for p in itertools.permutations(a, len(a)):
if b.find(''.join(p)) >= 0:
return True
return False

for w1, w2 in (('cat', 'actor'), ('car', 'actor')):
print("%s %s -> %s" % (w1, w2, anagram(w1, w2)))
```
11. rock321987 said

Here is O(nk) solution using Sliding window algo..i was asked this question in amazon..i was not able to solve it there..is there more efficient approach??

```#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

int calc(string arr, string str)
{
if (arr.length() > str.length()) {
return -1;
}

int length = arr.length(), freqarr[255] = {0}, freqstr[255] = {0};

for (int i = 0;i < length;i++) {
freqarr[arr.at(i)]++;
freqstr[str.at(i)]++;
}

for (int i = 0;i <= str.length() - length;i++) {
int flag = 0;

for (int j = i;j < i + length;j++) {
char tmp = str.at(j);
//printf("%c\n", tmp);
if (freqarr[tmp] >= freqstr[tmp]) {

} else {
flag = 1;
break;
}
}

if (flag == 0) {
return i;
} else {
if (i != str.length() - length) {
freqstr[str.at(i)]--;
freqstr[str.at(i + length)]++;
}
}
}
return -1;
}

int main()
{
while (1) {
string arr, str;
cin >> arr >> str;

int x = calc(arr, str);

if (x == -1) {