21
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Must the truthy and falsey value be consistent or just appropriately truthy or falsey? \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 13:17
  • \$\begingroup\$ @EriktheOutgolfer just appropriate is fine. \$\endgroup\$ – Notts90 May 26 '17 at 15:04

20 Answers 20

14
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ Right tool for the job. \$\endgroup\$ – isaacg May 27 '17 at 8:52
7
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ This is much faster than the versions that use permutations. \$\endgroup\$ – David Conrad May 26 '17 at 17:20
6
\$\begingroup\$

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))]
\$\endgroup\$
  • 1
    \$\begingroup\$ Save a byte by naming sorted. \$\endgroup\$ – Jonathan Allan May 26 '17 at 12:56
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I don't think you need . \$\endgroup\$ – Emigna May 26 '17 at 12:02
  • \$\begingroup\$ Not sure if it's my phone but TIO seems broken, says language not found. \$\endgroup\$ – Notts90 May 26 '17 at 12:03
  • \$\begingroup\$ @Notts90 It's TIO v2 not TIO Nexus, try to clear your cache. It works for me. \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 12:04
  • \$\begingroup\$ @Emigna Apparently "vectorized" means the second argument not the first... \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 12:05
  • 2
    \$\begingroup\$ If only you'd put the crossed out 4 \$\endgroup\$ – Neil A. May 26 '17 at 14:42
5
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ In C# a void lambda is Action<params> instead of Func<params, returnVal>. I assume it would be something similar. \$\endgroup\$ – TheLethalCoder May 26 '17 at 13:48
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen May 26 '17 at 14:16
  • \$\begingroup\$ Nice, at least you figured it out \$\endgroup\$ – TheLethalCoder May 26 '17 at 14:17
  • \$\begingroup\$ I used a Function<String, Predicate<String>> in mine. \$\endgroup\$ – David Conrad May 26 '17 at 18:58
5
\$\begingroup\$

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 
\$\endgroup\$
5
\$\begingroup\$

Japt, 10 7 bytes

á d!èV

Try it online


Explanation

á d@VèX  
         :Implicit input of (sub)string U
á        :Create an array of all possible permutations of U
  d      :Map over the array, checking if any element returns true for...
   @     :the function that checks..
     è   :the number of matches...
      X  :of current element (permutation) X...
    V    :in main string V.
         :(0 is falsey, anything else is truthy)
         :Implicit output of result
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can also have lambda as parameter : lambda u,t,s=sorted: for an one-liner, no byte saved though \$\endgroup\$ – Rod May 26 '17 at 14:02
  • \$\begingroup\$ @cat the assignment is required since the function is recursive. \$\endgroup\$ – Jonathan Allan May 28 '17 at 14:50
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ OP said that it can be just truthy/falsey, not necessarily consistent, so you can use s instead of }1. \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 15:17
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ The output only needs to be "truthy/falsey" not literal True/False. \$\endgroup\$ – Ian Miller May 27 '17 at 8:24
  • \$\begingroup\$ Thanks for reminder about Characters. \$\endgroup\$ – Ian Miller May 27 '17 at 8:24
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I think this is invalid, what about inputs a and abc? \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 13:34
  • \$\begingroup\$ @EriktheOutgolfer You are right. It should be a >=0 instead of >0 \$\endgroup\$ – FrodCube May 26 '17 at 13:37
  • 1
    \$\begingroup\$ But you can do W>. \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 13:38
  • \$\begingroup\$ @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? \$\endgroup\$ – FrodCube May 26 '17 at 13:44
  • \$\begingroup\$ You can use ) instead of W>, per OP's clarification. \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 15:19
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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++);
        }
}
\$\endgroup\$
  • \$\begingroup\$ yeah, unfortunately using linq often makes things longer than simple for(..){} \$\endgroup\$ – Ewan May 27 '17 at 11:09
2
\$\begingroup\$

Ruby, 69 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Try ~$p instead of a&$p. \$\endgroup\$ – Titus May 27 '17 at 7:50
  • \$\begingroup\$ When I try to run your code using the link it says unexpected , \$\endgroup\$ – Notts90 May 27 '17 at 7:58
  • \$\begingroup\$ @Notts90 Please use a PHP Version over 7.1 \$\endgroup\$ – Jörg Hülsermann May 27 '17 at 9:10
  • \$\begingroup\$ @JörgHülsermann that works, it had defaulted to 7.0.3 \$\endgroup\$ – Notts90 May 27 '17 at 9:12
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog), 18 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

MATL, 10 bytes

Y@Z{w&Xfma

Try it on MATL Online

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.