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

22 Answers 22

15
\$\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\$
1
  • 4
    \$\begingroup\$ Right tool for the job. \$\endgroup\$
    – isaacg
    May 27, 2017 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\$
1
  • 2
    \$\begingroup\$ This is much faster than the versions that use permutations. \$\endgroup\$ May 26, 2017 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
  • 1
    \$\begingroup\$ Save a byte by naming sorted. \$\endgroup\$ May 26, 2017 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\$
6
  • \$\begingroup\$ I don't think you need . \$\endgroup\$
    – Emigna
    May 26, 2017 at 12:02
  • \$\begingroup\$ Not sure if it's my phone but TIO seems broken, says language not found. \$\endgroup\$ May 26, 2017 at 12:03
  • \$\begingroup\$ @Notts90 It's TIO v2 not TIO Nexus, try to clear your cache. It works for me. \$\endgroup\$ May 26, 2017 at 12:04
  • \$\begingroup\$ @Emigna Apparently "vectorized" means the second argument not the first... \$\endgroup\$ May 26, 2017 at 12:05
  • 2
    \$\begingroup\$ If only you'd put the crossed out 4 \$\endgroup\$
    – Neil A.
    May 26, 2017 at 14:42
6
\$\begingroup\$

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
\$\endgroup\$
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\$
4
  • \$\begingroup\$ In C# a void lambda is Action<params> instead of Func<params, returnVal>. I assume it would be something similar. \$\endgroup\$ May 26, 2017 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\$ May 26, 2017 at 14:16
  • \$\begingroup\$ Nice, at least you figured it out \$\endgroup\$ May 26, 2017 at 14:17
  • \$\begingroup\$ I used a Function<String, Predicate<String>> in mine. \$\endgroup\$ May 26, 2017 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\$
0
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\$
2
  • \$\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, 2017 at 14:02
  • \$\begingroup\$ @cat the assignment is required since the function is recursive. \$\endgroup\$ May 28, 2017 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\$
1
  • \$\begingroup\$ OP said that it can be just truthy/falsey, not necessarily consistent, so you can use s instead of }1. \$\endgroup\$ May 26, 2017 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\$
2
  • \$\begingroup\$ The output only needs to be "truthy/falsey" not literal True/False. \$\endgroup\$
    – Ian Miller
    May 27, 2017 at 8:24
  • \$\begingroup\$ Thanks for reminder about Characters. \$\endgroup\$
    – Ian Miller
    May 27, 2017 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\$
5
  • \$\begingroup\$ I think this is invalid, what about inputs a and abc? \$\endgroup\$ May 26, 2017 at 13:34
  • \$\begingroup\$ @EriktheOutgolfer You are right. It should be a >=0 instead of >0 \$\endgroup\$
    – FrodCube
    May 26, 2017 at 13:37
  • 1
    \$\begingroup\$ But you can do W>. \$\endgroup\$ May 26, 2017 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, 2017 at 13:44
  • \$\begingroup\$ You can use ) instead of W>, per OP's clarification. \$\endgroup\$ May 26, 2017 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
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\$
1
  • \$\begingroup\$ yeah, unfortunately using linq often makes things longer than simple for(..){} \$\endgroup\$
    – Ewan
    May 27, 2017 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\$
0
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\$
4
  • 1
    \$\begingroup\$ Try ~$p instead of a&$p. \$\endgroup\$
    – Titus
    May 27, 2017 at 7:50
  • \$\begingroup\$ When I try to run your code using the link it says unexpected , \$\endgroup\$ May 27, 2017 at 7:58
  • \$\begingroup\$ @Notts90 Please use a PHP Version over 7.1 \$\endgroup\$ May 27, 2017 at 9:10
  • \$\begingroup\$ @JörgHülsermann that works, it had defaulted to 7.0.3 \$\endgroup\$ May 27, 2017 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\$
1
\$\begingroup\$

MATL, 10 bytes

Y@Z{w&Xfma

Try it on MATL Online

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

Ruby, 43 bytes

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

Attempt This Online!

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

APL (Dyalog), 18 bytes

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

Try it online!

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

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.

\$\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.