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

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]
[4,19]
[0]
[]
```
8. NATTY said

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";
}
}

}

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