My [sub] strings are hiding!

Question

Introduction

A while ago a lost SO user posted a question here and its now been deleted but I think it would make a good challenge so here it goes...

Challenge

Write a full program or function that takes two strings and checks whether any permutation of the first string is a sub-string of the second string.

Input

Two strings, a string and a sub-string to test for (you may choose the order).

Output:

A truthy value if the string contains any permutation of the sub-string.
A falsey value if the string does not contain any permutations of the the sub-string.
The test is case sensitive.

Examples/Test cases

         sub-string    string          
input    d!rl          Hello World!
output   truthy

input    Pog           Programming Puzzles & Code Golf
output   falsey

input    ghjuyt        asdfhytgju1234
output   truthy

Answer 1

Brachylog, 2 bytes

sp

Try it online!

Explanation

Input variable = "Hello World!", Output variable = "d!rl"

(?)s        Take a substring of the Input variable
    p(.)    It is a permutation of the Output variable

Answer 2

JavaScript (ES6), 77 bytes

(s,t)=>t&&[...t.slice(0,s.length)].sort()+''==[...s].sort()|f(s,t.slice(1))

Returns 1 or 0.

Snippet

f=

(s,t)=>t&&[...t.slice(0,s.length)].sort()+''==[...s].sort()|f(s,t.slice(1))

console.log(f('d!rl','Hello World!'))                   //1
console.log(f('Pog','Programming Puzzles & Code Golf')) //0
console.log(f('ghjuyt','asdfhytgju1234'))               //1

Answer 3

Python 2, 67 66 bytes

Takes input as two strings, substring first.

a=sorted
lambda s,S:a(s)in[a(S[n:n+len(s)])for n in range(len(S))]

Answer 4

05AB1E, 3 bytes

όZ

Try it online!

-1 byte thanks to Emigna.

Explanation:

όZ 2 inputs
œ                  permutations of the first input
 å  Is each of the                                 in the second input?
  Z Take the maximum of the resulting boolean list

Answer 5

Japt, 10 7 6 bytes

á d!øV

Try it online

á d!øV   :Implicit input of sub-string U & string V
á        :Permutations of U
  d      :Any
   !øV   :  Contained in V

Answer 6

Java 8, 266 244 bytes

import java.util.*;Set l=new HashSet();s->p->{p("",p);for(Object x:l)if(s.contains(x+""))return 1>0;return 0>1;}void p(String p,String q){int n=q.length(),i=0;if(n<1)l.add(p);else for(;i<n;)p(p+q.charAt(i),q.substring(0,i)+q.substring(++i,n));}

Explanation:

Try it here.

java.util.*;                   // Required import for Set and HashSet

Set l=new HashSet();           // Class-level Set

s->p->{                        // Method (1) with two String parameters and boolean return-type
  p("",p);                     //  Put all permutations in the class-level Set
  for(Object x:l)              //  Loop over the permutations:
    if(s.contains(x+""))       //   If the input String contains one of the permutations:
      return 1>0;//true        //    Return true
                               //  End of loop (implicit / single-line body)
  return 0>1;//false           //  Return false
}                              // End of method (1)

void p(String p,String q){     // Method (2) with two String parameters and no return-type
  int n=q.length(),i=0;        //  Two temp integers
  if(n<1)                      //  If `n` is zero:
    l.add(p);                  //   Add this permutation of the String to the Set
  else                         //  Else:
    for(;i<n;                  //   Loop over `n`
      p(p+q.charAt(i),q.substring(0,i)+q.substring(++i,n))
                               //    Recursive-call with permutation parts
    );                         //   End of loop (no body)
}                              // End of method (2)

Answer 7

Jelly, 5 bytes

Œ!ẇ€Ṁ

Try it online!

-1 thanks to Emigna for encouraging me to retry golfing.

Explanation:

Œ!ẇ€Ṁ Main link, dyadic
Œ!               the permutations of the left argument
  ẇ€  Is each of                                      in the right argument?
    Ṁ Maximum of boolean values 

Answer 8

Python, 60 bytes

An altered form of TFeld's answer - go give some credit!

s=sorted
f=lambda u,t:s(u)==s(t[:len(u)])or t and f(u,t[1:])

Recursive function returning the boolean True (truthy) or an empty string (falsy).

Try it online!

sorts the substring, u, and the same length of the front of the string, t, (using a slice t[:len(u)]) if they are the same then True is returned, otherwise if t is still truthy (not empty) recurses with a dequeued t (using a slice, t[1:]). If t does become empty the and is not executed and this empty t is returned.

Answer 9

Pyth, 9 8 bytes

sm}dQ.pE

-1 byte thanks to @Erik_the_Outgolfer

Takes two quoted strings, the second of which is the substring.

Try it!

Answer 10

Mathematica, 55 50 bytes

-5 bytes from user202729

StringFreeQ[#2,""<>#&/@Permutations@Characters@#]&

Returns False if a permutation of the first input is in the second string. Returns True if a permutation of the first input is not in the second string.

Explanation:

                                    Characters@#   - split first string into array of characters
                       Permutations@               - make all permutations
               ""<>#&/@                            - join each array of characters together to form a single string
StringFreeQ[#2,                                 ]& - Check if any of these string is in the second input string

Answer 11

CJam, 13 12 bytes

le!lf{\#)}:+

Try it online!

I feel like CJam is really limited compared to other golfing languages, but maybe it's just me being bad...

I'm thinking about moving to another. 05AB1E seems fun.

Fixed small bug thanks to Erik the Outgolfer
Cut one bite because non-zero numbers are truthy

Explanation:

l                 Read substring
 e!               Generate all permutations
   l              Read string
    f{            For each permutation
      \#            Check if it is in the string (returns -1 if not found)
        )           Add one
         }        End for
          :+      Sum the whole found/not found array

Answer 12

Java 9 JShell, 160 bytes

p->q->IntStream.range(0,q.length()-p.length()+1).anyMatch(
    i->Arrays.equals(
        q.substring(i,i+p.length()).chars().sorted().toArray(),
        p.chars().sorted().toArray()))

(newlines inserted for readability)

Try it online!

Note: JShell includes a number of imports by default. As a Java 8 or Java 9 solution, it would be necessary to import:

import java.util.*;import java.util.stream.*;

For an extra 45 bytes, or 205 bytes total. The TIO link above is to a Java 9 program since TIO doesn't currently have JShell (and it's not clear to me how JShell would work on TIO).

Answer 13

C#, 320 bytes

using System.Linq;s=>u=>p(u.ToArray(),0,u.Length-1).Any(p=>s.Contains(p));w=(c,a,b)=>{if (a!=b)(var t=c[a];c[a]=c[b];c[b]=t;)};System.Collections.Generic.IEnumerable<string>p(char[]l,int k,int m){if(k==m)yield return new string(l);else for(int i=k;i<=m;){w(l,k,i);foreach(var c in p(l,k+1,m))yield return c;w(l,k,i++);}}

I'm sure calculating the permutations can be a lot shorter but I can't see how at the moment.

Formatted/Full version:

void test()
{
    Func<string, Func<string, bool>> f = s => u =>
        p(u.ToArray(), 0, u.Length - 1).Any(p => s.Contains(p));

    Console.WriteLine(f("Hello World!")("d!rl"));
    Console.WriteLine(f("Programming Puzzles & Code Golf")("Pog"));
    Console.WriteLine(f("asdfhytgju1234")("ghjuyt"));
}

System.Collections.Generic.IEnumerable<string>p(char[] l, int k, int m)
{
    Action<char[], int, int> w = (c, a, b) =>
    {
        if (a != b)
        {
            var t = c[a];
            c[a] = c[b];
            c[b] = t;
        }
    };

    if (k == m)
        yield return new string(l);

    else
        for (int i = k; i <= m;)
        {
            w(l, k, i);

            foreach (var c in p(l, k + 1, m))
                yield return c;

            w(l, k, i++);
        }
}

Answer 14

Ruby, 69 bytes

->a,b{r=nil;a.chars.each_cons(b.size){|q|r||=q.sort==b.chars.sort};r}

Try it online!

Answer 15

Perl 6, 48 bytes

{$^a.contains(any $^b.comb.permutations».join)}

Returns an or-junction of each permutation's presence as a substring. For example, with arguments "Hello World!" and "d!l", returns:

any(False, False, False, False, True, False)

...which "collapses" to True in a boolean context. That is, junctions are truthy values.

Answer 16

PHP>=7.1, 91 Bytes

for([,$x,$y]=$argv;~$p=substr($y,$i++,strlen($x));)$t|=($c=count_chars)($x)==$c($p);echo$t;

Testcases

Answer 17

Haskell, 54 bytes

import Data.List
s#t=any(`isInfixOf`s)$permutations t

Using the power of Data.List for both isInfixOf as well as permutations.

Answer 18

R, 103 bytes

function(w,x,y=u(w),z=u(x)){for(i in 1:n(w)){F=F|!sum(setdiff(y[1:n(x)+i-1],z))};F}
u=utf8ToInt
n=nchar

Try it online!

Returns TRUE for truthy and NA for falsey.

Answer 19

MATL, 10 bytes

Y@Z{w&Xfma

Try it on MATL Online

Answer 20

Ruby, 43 bytes

->a,b{b.chars.permutation.any?{|c|a[c*""]}}

Attempt This Online!

Answer 21

APL (Dyalog), 18 bytes

{∨/(∧/⍺∊⊢)¨⍵,/⍨⍴⍺}

Try it online!

Answer 22

Factor + math.combinatorics, 35 bytes

[ '[ _ subseq? ] find-permutation ]

Try it online!

Outputs the matching subsequence (which behaves as boolean true in Factor) for truthy and f for falsey.