A Fun Little Task
February 28, 2017
We sort string a, then slide a window of the length of string a along string b, at each step comparing the sorted a to the sorted substring of b. Instead of sorting each substring of b, we sort only the first substring, then repeatedly remove the oldest character and add the newest character to the sorted substring:
(define (f a b)
(let* ((a-len (string-length a))
(b-len (string-length b))
(target (sort char<? (string->list a)))
(window (sort char<? (string->list
(substring b 0 a-len)))))
(let loop ((i 0) (j a-len) (window window))
(cond ((= j b-len) #f)
((equal? target window) i)
(else (loop (+ i 1) (+ j 1)
(insert char<? (string-ref b j)
(remove (string-ref b i) window))))))))
Auxiliary functions insert and remove insert an item into a list in order and remove the first occurrence of an item from a list:
(define (insert lt? x xs)
(let loop ((xs xs) (zs (list)))
(cond ((null? xs) (reverse (cons x zs)))
((lt? x (car xs))
(append (reverse zs) (list x) xs))
(else (loop (cdr xs) (cons (car xs) zs))))))
(define (remove x xs)
(let loop ((xs xs) (zs (list)))
(cond ((null? xs) (reverse zs))
((equal? x (car xs))
(append (reverse zs) (cdr xs)))
(else (loop (cdr xs) (cons (car xs) zs))))))
Here are some examples; 5 is the zero-based index of the beginning of the permutation:
> (f "xyz" "asdfgzyxpoiuy") 5 > (f "wxyz" "asdfgzywpoiuy") #f
You can run the program at http://ideone.com/ERm8Tv.
Programming Praxis 
Isn’t this the same as https://programmingpraxis.com/2014/02/21/anagrams-within-words/ – I was thinking “Hmm, an incrementally modified multiset would do nicely here” and then I remembered https://programmingpraxis.com/2014/02/21/anagrams-within-words/#comment-19023 (possibly my first contribution here).
Shhh. You found my secret. Don’t tell anybody.
Indeed, we did this exercise before. Here another Python version.
from collections import deque from itertools import islice def slidingwindow(iterable, n=2): """return sliding window as deque's""" it = iter(iterable) deq = deque(islice(it, n), maxlen=n) yield deq app = deq.append for i in it: app(i) yield deq def is_part_perm1(a, b): sorta = sorted(a) return any(sorted(wb) == sorta for wb in slidingwindow(b, n=len(a)))I don’t see this python solution in either exercise.
Use itertools.groupby() on the second string to collect runs of characters that are in the first string. Then, use collections.Counter as a multiset to compare a multiset of each run with a multiset of the first string. Linear complexity, I think.
from collections import Counter as Multiset from itertools import groupby def is_permuted_substring(a,b): ma = Multiset(a) runs = (g for k,g in groupby(b, key=ma.__contains__) if k) return any(ma == Multiset(run) for run in runs)@Mike: your method returns False for (a, b) = (“xxx”, “xxxx”). You still have to make sure that your runs have the same length as a.
A solution in Racket.
A Haskell version.
import Data.Set (fromList, member) -- Return the 0-based positions in ys at which a permutation of xs begins, or -- the empty list if there are none. The permuation must consist of consecutive -- elements. subPerm :: Ord a => [a] -> [a] -> [Int] subPerm xs ys = let m = fromList xs n = length xs - 1 zs = map snd $ filter ((`member` m) . fst) $ zip ys [0..] in map fst $ filter (\(i,j) -> i+n == j) $ zip zs $ drop n zs main :: IO () main = do let s = "afdgzyxksldfm" print $ subPerm "xyz" s print $ subPerm "xyz" (s ++ reverse s) print $ subPerm "xxx" "xxx" print $ subPerm "xxx" "xxz"sub present{
@c = split(“”,$b);
print “$c[0]$c[1]$c[2]\n”;
$len = length($b);
for($i = 0;$i<=$len;$i++)
{
$x=$c[$i].$c[$i+1].$c[$i+2];
if($a eq $x)
{
print "YES\n";
}
}
}
Another Python version.
from itertools import product
def check(str_1, str_2):
s_1 = ''.join(sorted(str_1))
pos = [i for i,x in enumerate(str_2) if x == s_1[0]]
return any(j-k >= 0 and s_1 == ''.join(sorted(str_2[j-k:j+len(str_1)-k]))
for j, k in product(pos, range(len(str_1))))