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.

Advertisements

Pages: 1 2

7 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

    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"
    
    $ ./subperm 
    [4]
    [4,19]
    [0]
    []
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: