Moje [pod] struny się ukrywają!

21

Wprowadzenie

Jakiś czas temu zagubiony użytkownik SO opublikował tutaj pytanie, które teraz zostało usunięte, ale myślę, że stanowiłoby dobre wyzwanie, więc proszę ...

Wyzwanie

Napisz pełny program lub funkcję, która pobiera dwa ciągi znaków i sprawdza, czy permutacja pierwszego ciągu jest podciągiem drugiego ciągu.

Wkład

Dwa ciągi, ciąg i podciąg dla testowania (możesz wybrać kolejność).

Wydajność:

Prawdziwa wartość, jeśli ciąg zawiera permutację podciągu.
Wartość falsey, jeśli ciąg nie zawiera żadnych permutacji podciągu.
W teście rozróżniana jest wielkość liter.

Przykłady / przypadki testowe

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

input    Pog           Programming Puzzles & Code Golf
output   falsey

input    ghjuyt        asdfhytgju1234
output   truthy
Notts90
źródło
Czy wartość prawdy i falseya musi być spójna, czy po prostu odpowiednio prawdomówna lub falsey?
Erik the Outgolfer
@EriktheOutgolfer po prostu odpowiednie jest w porządku.
Notts90

Odpowiedzi:

14

Brachylog , 2 bajty

sp

Wypróbuj online!

Wyjaśnienie

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
Fatalizować
źródło
4
Odpowiednie narzędzie do pracy.
isaacg
7

JavaScript (ES6), 77 bajtów

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

Zwraca 1 lub 0.

Skrawek

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

Rick Hitchcock
źródło
2
Jest to znacznie szybsze niż wersje korzystające z permutacji.
David Conrad
6

Python 2, 67 66 bajtów

Pobiera dane wejściowe jako dwa ciągi, najpierw podłańcuch.

a=sorted
lambda s,S:a(s)in[a(S[n:n+len(s)])for n in range(len(S))]
TFeld
źródło
1
Zapisz bajt, nazywając go sorted.
Jonathan Allan
6

05AB1E , 3 bajty

όZ

Wypróbuj online!

-1 bajt dzięki Emignie .

Wyjaśnienie:

ό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
Erik the Outgolfer
źródło
Nie sądzę, że potrzebujesz.
Emigna
Nie jestem pewien, czy to mój telefon, ale TIO wydaje się zepsuty, mówi, że nie znaleziono języka.
Notts90
@ Notts90 To TIO v2, a nie TIO Nexus, spróbuj wyczyścić pamięć podręczną. Mi to pasuje.
Erik the Outgolfer
@Emigna Najwyraźniej „wektoryzowany” oznacza drugi argument, a nie pierwszy ...
Erik the Outgolfer
2
Gdybyś tylko umieścił przekreślony 4
Neil A.
5

Java 8, 266 244 bajtów

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

Wyjaśnienie:

Wypróbuj tutaj.

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)
Kevin Cruijssen
źródło
W języku C # Action<params>zamiast jest pusta lambda Func<params, returnVal>. Zakładam, że byłoby to coś podobnego.
TheLethalCoder
1
@TheLethalCoder Masz rację. Powinien użyć Consumeri accept(...)zamiast Functioni apply(...)kiedy chcę mieć lambda z parametrem i bez typu zwracanego. Obecnie uczę się Java 8. :) Ale ponieważ muszę się zmienić void p(String p,String q), p("",p);i p(p+q.ch...,q.sub...)do p->q->, p.apply("").accept(p);i p.apply(p+q.ch...).accept(q.sub...)krótsze jest użycie kombinacji lambda dla głównej metody i tylko void p(String p,String q)metody Java 7 dla metody rekurencyjnej.
Kevin Cruijssen
Fajnie, przynajmniej to wymyśliłeś
TheLethalCoder
Użyłem Function<String, Predicate<String>>mojego.
David Conrad
5

Galaretka , 5 bajtów

Œ!ẇ€Ṁ

Wypróbuj online!

-1 dzięki Emignie za zachęcenie mnie do ponownej gry w golfa.

Wyjaśnienie:

Œ!ẇ€Ṁ Main link, dyadic
Œ!               the permutations of the left argument
  ẇ€  Is each of                                      in the right argument?
    Ṁ Maximum of boolean values 
Erik the Outgolfer
źródło
5

Japt, 10 7 bajtów

á d!èV

Wypróbuj online


Wyjaśnienie

á 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
Kudłaty
źródło
4

Python , 60 bajtów

Zmieniona forma odpowiedzi TFelda - idź, daj kredyt!

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

Funkcja rekurencyjna zwracająca wartość logiczną True(prawda) lub pusty ciąg (fałsz).

Wypróbuj online!

sortuje podłańcuch ui tę samą długość przodu łańcucha t(przy użyciu plasterka t[:len(u)]), jeśli są one takie same, wówczas Truejest zwracane, w przeciwnym razie, jeśli tnadal jest zgodne z prawdą (nie puste), powtarza się z kolejką odwrotną t(przy użyciu plasterka t[1:]) . Jeśli tstanie się puste, andto nie zostanie wykonane, a to puste tzostanie zwrócone.

Jonathan Allan
źródło
Jako parametr można również podać lambda: lambda u,t,s=sorted:dla liniowej nie zapisano bajtu
Rod
@cat przypisanie jest wymagane, ponieważ funkcja jest rekurencyjna.
Jonathan Allan
4

Pyth, 9 8 bajtów

sm}dQ.pE

-1 bajt dzięki @Erik_the_Outgolfer

Pobiera dwa cytowane ciągi, z których drugim jest podłańcuch.

Spróbuj!

KarlKastor
źródło
OP powiedział, że może to być po prostu prawda / falsey, niekoniecznie spójne, więc możesz użyć szamiast }1.
Erik the Outgolfer
3

Mathematica, 55 50 bajtów

-5 bajtów od user202729

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

Zwraca, Falsejeśli permutacja pierwszego wejścia znajduje się w drugim ciągu. Zwraca, Truejeśli permutacja pierwszego wejścia nie znajduje się w drugim ciągu.

Wyjaśnienie:

                                    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
źródło
Wynik musi być tylko „prawdy / falsey”, a nie dosłowny True/ False.
Ian Miller
Dzięki za przypomnienie Characters.
Ian Miller
3

CJam , 13 12 bajtów

le!lf{\#)}:+

Wypróbuj online!

Wydaje mi się, że CJam jest naprawdę ograniczony w porównaniu do innych języków golfowych, ale może po prostu jestem zły ...

Myślę o przeprowadzce do innej. 05AB1E wydaje się zabawny.

Naprawiono mały błąd dzięki Erikowi Outgolfer
Cut jeden kęs, ponieważ niezerowe liczby są prawdziwe

Wyjaśnienie:

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
FrodCube
źródło
Myślę, że to jest nieprawidłowe, co z danymi wejściowymi ai abc?
Erik the Outgolfer
@EriktheOutgolfer Masz rację. Powinno to być> = 0 zamiast> 0
FrodCube
1
Ale możesz zrobić W>.
Erik the Outgolfer
@EriktheOutgolfer byłoby le!lf{\#)}:+uważane za prawidłowe rozwiązanie? Powinien być wyprowadzany, 0jeśli łańcuch nie zostanie znaleziony, a w przeciwnym razie dodatnia liczba. Czy liczba niezerowa jest poprawna truthy?
FrodCube
Możesz użyć )zamiast W>, zgodnie z wyjaśnieniem PO.
Erik the Outgolfer
3

Java 9 JShell , 160 bajtów

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

(wstawiono nowe wiersze dla czytelności)

Wypróbuj online!

Uwaga: JShell domyślnie zawiera pewną liczbę importów. Jako rozwiązanie Java 8 lub Java 9 konieczne byłoby zaimportowanie:

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

Dla dodatkowych 45 bajtów lub łącznie 205 bajtów. Powyższe łącze TIO prowadzi do programu Java 9, ponieważ TIO nie ma obecnie JShell (i nie jest dla mnie jasne, jak JShell będzie działał na TIO).

David Conrad
źródło
Java 9 to już coś? : |
CalculatorFeline
@CalculatorFeline Kompilacje wczesnego dostępu były dostępne od dłuższego czasu, ale oficjalna data wydania to 27.07.2017 .
David Conrad
2

C #, 320 bajtów

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

Jestem pewien, że obliczanie permutacji może być o wiele krótsze, ale w tej chwili nie wiem, jak to zrobić.

Sformatowana / Pełna wersja:

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++);
        }
}
TheLethalCoder
źródło
tak, niestety korzystanie z linq często sprawia, że ​​rzeczy są dłuższe niż proste dla (..) {}
Ewan
2

Rubinowy , 69 bajtów

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

Wypróbuj online!

Alex
źródło
2

Perl 6 , 48 bajtów

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

Zwraca łącznik obecności każdej permutacji jako podłańcuch. Na przykład z argumentami "Hello World!"i "d!l"zwraca:

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

... który „zapada się” Truew kontekście logicznym. Oznacza to, że skrzyżowania są prawdziwymi wartościami.

Sean
źródło
2

PHP> = 7,1, 91 bajtów

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

Przypadki testowe

Jörg Hülsermann
źródło
1
Spróbuj ~$pzamiast a&$p.
Tytus
Gdy próbuję uruchomić kod za pomocą linku, ,
pojawia się komunikat
@ Notts90 Proszę używać wersji PHP powyżej 7.1
Jörg Hülsermann
@ JörgHülsermann, który działa, domyślnie był
ustawiony na 7.0.3
1

Haskell, 54 bajty

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

Wykorzystanie mocy Data.List zarówno dla, isInfixOfjak i dla permutations.

wałek klonowy
źródło
1

R , 103 bajty

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

Wypróbuj online!

Zwraca TRUEza prawdę i NAfalsey.

ngm
źródło