A Fun Little Task
February 28, 2017
Today’s exercise is a fun little task:
Given two strings a and b, with a no longer than b, determine if there is any permutation of a that appears in b. For instance, a permutation of string xyz appears starting at the fourth character (counting from zero) of string afdgzyxksldfm.
Your task is to write a program to determine is any permutation of a string is a substring of another string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Advertisements
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))))