### 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.

Pages: 1 2

### 9 Responses to “A Fun Little Task”

1. matthew said

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).

2. programmingpraxis said

Shhh. You found my secret. Don’t tell anybody.

3. Paul said

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)))
```
4. Mike said

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)

```
5. Paul said

@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.

6. r. clayton said

A solution in Racket.

7. Globules said

```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"
```
```\$ ./subperm

[4,19]

[]
```
8. NATTY said

sub present{

@c = split(“”,\$b);
print “\$c\$c\$c\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";
}
}

}

9. Eric said

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] 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)))) ```