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

• Erik the Outgolfer: Must the truthy and falsey value be consistent or just appropriately truthy or falsey?
• Notts90: @EriktheOutgolfer just appropriate is fine.

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

• izzyg: Right tool for the job.

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

• David Conrad: This is much faster than the versions that use permutations.

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

• Jonathan Allan: Save a byte by naming sorted.

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

• Emigna: I don't think you need .
• Notts90: Not sure if it's my phone but TIO seems broken, says language not found.
• Erik the Outgolfer: @Notts90 It's TIO v2 not TIO Nexus, try to clear your cache. It works for me.
• Erik the Outgolfer: @Emigna Apparently "vectorized" means the second argument not the first...
• Neil A.: If only you'd put the crossed out 4

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)

• TheLethalCoder: In C# a void lambda is Action<params> instead of Func<params, returnVal>. I assume it would be something similar.
• Kevin Cruijssen: @TheLethalCoder You're right. Should use Consumer and accept(...) instead of Function and apply(...) when I want to have a lambda with a parameter and no return-type. I'm currently learning Java 8. :) But since I'll have to change void p(String p,String q), p("",p); and p(p+q.ch...,q.sub...) to p->q->, p.apply("").accept(p); and p.apply(p+q.ch...).accept(q.sub...) it is shorter to use a combination of lambda for the main method, and just a Java 7 void p(String p,String q) method for the recursive-method.
• TheLethalCoder: Nice, at least you figured it out
• David Conrad: I used a Function<String, Predicate<String>> in mine.

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.

• Rod: You can also have lambda as parameter : lambda u,t,s=sorted: for an one-liner, no byte saved though
• Jonathan Allan: @cat the assignment is required since the function is recursive.

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!

• Erik the Outgolfer: OP said that it can be just truthy/falsey, not necessarily consistent, so you can use s instead of }1.

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

• Ian Miller: The output only needs to be "truthy/falsey" not literal True/False.
• Ian Miller: Thanks for reminder about Characters.

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

• Erik the Outgolfer: I think this is invalid, what about inputs a and abc?
• FrodCube: @EriktheOutgolfer You are right. It should be a >=0 instead of >0
• Erik the Outgolfer: But you can do W>.
• FrodCube: @EriktheOutgolfer would le!lf{\#)}:+ be considered a valid solution? It should output 0 if the string is not found and some positive number otherwise. Is a non-zero number a valid truthy?
• Erik the Outgolfer: You can use ) instead of W>, per OP's clarification.

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

• CalculatorFeline: Java 9 is a thing now? :|
• David Conrad: @CalculatorFeline The early access builds have been available for quite some time, but the official release date is 2017年07月27日.

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++);
 }
}

• Ewan: yeah, unfortunately using linq often makes things longer than simple for(..){}

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

• Titus: Try ~$p instead of a&$p.
• Notts90: When I try to run your code using the link it says unexpected ,
• Jörg Hülsermann: @Notts90 Please use a PHP Version over 7.1
• Notts90: @JörgHülsermann that works, it had defaulted to 7.0.3

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.