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
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’]
for i in posibilidades:
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
>>>
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/* header files */
#include // get access to printf() and scanf()
#include // get access to boolean values
#include // get access to strlen()
/* 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
}
http://pastebin.com/Lc3CR0n1
Lazy solution in Clojure using math.combinatorics/permutations:
http://pastebin.com/NHwcLt4M
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)
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;
}
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();
}
In Haskell:
http://codepad.org/0J61y6m6
[…] implemented the Anagrams Within Words programming puzzle from Programming Praxis in Python, a language I haven’t used since my […]
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) {} void add(Element c) { 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++) { mset.sub(s[i]); mset.add(t[i]); } if (mset.size() == 0) printf(" %d", 0); for(int i = slen; i < tlen; i++) { mset.sub(t[i-slen]); mset.add(t[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"); }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)))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) { printf("Not Found\n"); } else { printf("Found\n"); } } return 0; }