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

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: