Finden von "Subpalindromen".

24

Der kürzeste Code, der alle eindeutigen "Sub-Palindrome" einer Zeichenfolge findet, d. H. Alle Teilzeichenfolgen mit einer Länge> 1, die ein Palindrom sind.

zB.1

input: "12131331"
output: "33", "121", "131", "313", "1331"

zB.2

input: "3333"
output: "33", "333", "3333"
Eelvex
quelle
1
Kann eine Saite ein eigenes Subpalindrom sein? Da ein String ein eigener Teilstring ist.
JPvdMerwe
@JPvdMerwe: Ja, natürlich.
Eelvex
Eigentlich noch wichtiger: Was muss der Output von 333sein? Naiv würden Sie am Ende 33zweimal drucken
JPvdMerwe
@JPvdMerwe: '333' -> '33', '333'. Ich werde die Frage entsprechend bearbeiten. Vielen Dank.
Eelvex
Wie ist der Output spezifiziert? Kommagetrennt mit Anführungszeichen sind um jedes Subpalindrom, wie Sie hier demonstrieren? Ein Unter-P pro Zeile?
Joey

Antworten:

11

J, 24, 31, 40

~.(#~(1<#*]-:|.)&>),<\\.

Beispielgebrauch:

   ~.(#~(1<#*]-:|.)&>),<\\. '12131331'
┌───┬───┬───┬────┬──┐
│121│131│313│1331│33│
└───┴───┴───┴────┴──┘
   ~.(#~(1<#*]-:|.)&>),<\\. '3333'
┌──┬───┬────┐
│33│333│3333│
└──┴───┴────┘

Nehmen Sie das, GolfScript!

JB
quelle
Gib es zu, du hast von /dev/randomhier aus eine Müllkippe angelegt , um uns zum Narren zu halten ;-)
Joey,
@Joey, versuch es selbst; p (TBH, ich habe zunächst nicht geglaubt, dass es auch nicht funktionieren könnte)
JB
Ich bin mir ziemlich sicher, dass es sich um tatsächlichen Code handelt. Ich verbrachte ein Wochenende damit, meinen Kopf um J zu wickeln, scheiterte aber kläglich. Trotzdem erkenne ich Code. Ich verstehe nur nicht, was es tut ;-)
Joey
2
Kann das nicht auf ~.(#~(1<#*]-:|.)&>),<\\.(24 Zeichen) gekürzt werden ?
ephemient
@ephemient Tatsächlich. (Sieht so aus, als wäre ich in der Einstellung "Antwort muss eine Funktion sein" festgefahren, die hier nicht zutrifft.) Bearbeitet, danke!
JB
7

Python 124

r=raw_input()
l=range(len(r))
print', '.join(set('"'+r[i:j+1]+'"'for i in l for j in l if i<j and r[i:j+1]==r[i:j+1][::-1]))
Alexandru
quelle
5

Haskell 98, 88 91 96

import List
main=interact$show.filter(\x->length x>1&&x==reverse x).nub.(tails=<<).inits
JB
quelle
3

Python - 138 136

Dieser Code dupliziert keine Subpalindrome.

r=raw_input()
i,l=0,len(r)
j=l
a=[]
while i<l-1:
 t=r[i:j];j-=1
 if t==t[::-1]:a+=['"'+t+'"']
 if j<i+2:i+=1;j=l
print", ".join(set(a))
JPvdMerwe
quelle
1
Ändern Sie '"'+t+'"'zu t, um Platz zu sparen, obwohl einfache Anführungszeichen verwendet werden.
Thomas O
3

Ruby - 126 102 97 Zeichen

s=gets
*m=*0..s.size
puts m.product(m).map{|h,j|(c=s[h,j+1]).size>1&&c==c.reverse ? c:0}.uniq-[0]
Nemo157
quelle
3

Golfscript, 48 Zeichen

subpalindrome.gs

{,}{(;}/{{,}{);}/}%{+}*{.,1>\.-1%=*},.&{`}%", "*

Verwendung:

echo "12131331" | ruby golfscript.rb subpalindrome.gs

Die erste Operation {,}{(;}/wandelt eine Zeichenfolge in eine Liste von nachfolgenden Teilzeichenfolgen um. Eine ähnliche Leading-Substrings-Transformation wird dann auf das Ergebnis abgebildet. Dann mit abflachen {+}*, mit dem Prädikat nach Palindromen filtern .,1>\.-1%=*, mit eindeutige Werte erfassen .&, dann hübsch drucken.

Es wäre sinnvoller, die Trailing-Substrings-Transformation als Block zu extrahieren und als Ersatz für Leading-Substrings nach dem Umkehren jedes Trailing-Substrings wiederzuverwenden, aber ich kann mir keine prägnante Methode dafür vorstellen.

roobs
quelle
2

Haskell - 170 , 153

import Data.List
import Data.Set
p a=fromList$[show x|x<-subsequences a,x==reverse x,length x>1]
main=getLine>>=(\x->putStrLn$intercalate", "$toList$p x)
Jonathan Sternberg
quelle
Ersetzen main=getLine>>=(\x->putStrLn$intercalate", "$toList$p x)durch main=getLine>>=putStrLn.intercalate", ".toList.p. Ich würde auch einen Anruf pdurch seinen Körper ersetzen .
Yasir Arsanukaev
Teilstrings / = subsequences! Ihr Programm meldet mehr Subpalindrome als die Referenzausgabe, zum Beispiel 1. ("1111" zum Beispiel)
JB
2

J, 48

f=:,@:".
h=:\\.
~.(#~10&<)((]h-:"0&f|.h)#[:f]h)

z.B

~.(#~10&<)((]h-:"0&f|.h)#[:f]h) '12131331'
121 131 313 1331 33
Eelvex
quelle
2

Prolog, 92

f(S,P):-append([_,X,_],S),X=[_,_|_],reverse(X,X),atom_codes(P,X).
p(S,R):-setof(P,f(S,P),R).

Beispielgebrauch:

?- p("12131331",R).
R = ['121', '131', '1331', '313', '33'].

?- p("3333",R).
R = ['33', '333', '3333'].
JB
quelle
2

Windows PowerShell, 104 109 111

0..($l=($s="$input").length-1)|%{($a=$_)..$l|%{-join$s[$a..$_]}}|sort -u|?{$_[1]-and$_-eq-join$_[$l..0]}

Dies erwartet die Eingabe von stdin und wirft alle gefundenen Palindrome pro Zeile auf stdout:

PS Home:\SVN\Joey\Public\SO\CG183> '12131331'| .\subp.ps1
33
121
131
313
1331

(Wenn cmdes ausgeführt wird, hat echo 12131331|powershell -file subp.ps1es nur $inputeine etwas andere Bedeutung, abhängig davon, wie das Skript aufgerufen wurde, aber es kann stdin sein, nur nicht interaktiv.)

2011-01-30 13:57 (111) - Erster Versuch.

2011-01-30 13:59 (109) - Inline-Variablendeklaration.

2011-06-02 13:18 (104) - Erneutes Finden von Teilzeichenfolgen durch Verbinden eines .Substring()Zeichen- Arrays anstelle eines Aufrufs und etwas mehr Inlining.

Joey
quelle
2

Q, 78

{a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}

Verwendung

q){a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}"12131331"
"121"
"131"
"313"
"1331"
"33"
q){a::x;(?)(,/)b@'(&:')({x~(|:)x}'')b:-1_1_'({(sublist[;a]')x,'1+c}')c::(!)(#)a}"3333"
"33"
"333"
"3333"
tmartin
quelle
2

Retina , 34 27 Bytes

&@!`(.)+.?(?<-1>\1)+(?(1)^)

Probieren Sie es online!

Die Testsuite benötigt eine M da sich eine weitere Phase anschließt, in der Leerzeilen zwischen Testfällen eingefügt werden.

Erläuterung

&@!`(.)+.?(?<-1>\1)+(?(1)^)

Drucken ( !) Sie alle eindeutigen ( @), überlappenden ( &) Übereinstimmungen des regulären Ausdrucks (.)+.?(?<-1>\1)+(?(1)^). Dies entspricht einem Palindrom mit einer Länge von 2 oder mehr, das Bilanzgruppen verwendet. Der Teil "Alle überlappenden Matches" hat eine Einschränkung: Wir können höchstens ein Match pro Startposition erzielen. Beginnen jedoch zwei Palindrome unterschiedlicher Länge an derselben Position, erscheint das kürzere Palindrom wieder am Ende des längeren Palindroms. Und da die Gier +längerer Übereinstimmungen Prioritäten setzt, bekommen wir sowieso alle Palindrome.

Martin Ender
quelle
2

05AB1E , 11 10 Bytes

ŒÙʒÂQ}žQSK

Probieren Sie es online!

Magische Kraken-Urne
quelle
1
9 Bytes
Scottinet
@ Scottinet schlägt fehl für Singles, EG1234142141410010101000
Magic Octopus Urn
1
Mit freundlichen Grüßen, aber nicht auf die gleiche Weise. o_O Es ist etwas los, das untersucht werden muss. In der Zwischenzeit ist hier eine 10-Byte-Version , die zu funktionieren scheint
Scottinet
Es gab einen Fehler mit Uniquify, den ich behoben habe. Jetzt antworten beide 11 Bytes und meine 9 Bytes arbeiten :-)
Scottinet
@scottinet Ihr 10-byter kann durch Änderung ein 9-byter als gut 1›zu . :)
Kevin Cruijssen
1

Perl, 112

$_=<>;chop;s/./$&$' /g;
map{/../&&$_ eq reverse&&$h{$_}++}split/ /
  for grep{s/./$`$& /g}split/ /;
print for keys %h
seltsam
quelle
1

JavaScript (ES6), 120 Byte

a=>{for(b=0,c=d=a.length,e=[];b<d;--c<b+2?(b++,c=d):1)(f=a.slice(b,c))==f.split``.reverse().join``&&e.push(f);return e}

Diese Funktion nimmt einen String als Eingabe und gibt ein Array aus.

Luke
quelle
1

Clojure, 81 Bytes

#(set(for[i(range 2(+(count %)1))p(partition i 1 %):when(=(reverse p)(seq p))]p))

forwar eine perfekte Übereinstimmung hier :) Könnte verwendet werden, :when(=(reverse p)p)wenn die Eingabe eine Liste von Zeichen oder eine vollständige Zeichenfolge war, die nicht als Palindrom gezählt wurde, tatsächlich könnte in diesem Fall der maximale Bereich iauch sein (count %).

Kompaktester Fall als Referenz:

#(set(for[i(range 2(count %))p(partition i 1 %):when(=(reverse p)p)]p))
NikoNyrh
quelle
1

Python, 83 102 Zeichen

s=lambda t:(t[1:]or())and(t,)*(t==t[::-1])+s(t[1:])+s(t[:-1])
print set(s(input()))

Die Phrase (t[1:]or())and...ist äquivalent zu(...)if t[1:]else() und speichert ein Zeichen! Darauf bin ich angesichts der Einsparungen sehr stolz.

Beispiel:

python x
"51112232211161"
set(['11', '22', '11122322111', '161', '111', '112232211', '1223221', '22322', '232'])
boothby
quelle
1

Scala 127

object p extends App{val s=args(0);print(2.to(s.size).flatMap(s.sliding(_).toSeq.filter(c=>c==c.reverse)).toSet.mkString(" "))}

Um dies und den Vergleich von Apfel zu Apfel mit der anderen Antwort von Scala zu halten, habe ich mir auch ein Objekt gemacht, das App erweitert. Anstatt die Eingabezeichenfolge manuell zu iterieren und Teilzeichenfolgen zu verwenden, habe ich slide () verwendet, um eine Sequenz aller Teilzeichenfolgen für mich zu erstellen.

bkuder
quelle
1

Scala 156 170

object o extends App{val l=args(0).length-2;val r=for(i<-0 to l;j<-i to l;c=args(0).substring(i,j+2);if(c==c.reverse))yield c;print(r.toSet.mkString(" "))}

object o{def main(s:Array[String]){val l=s(0).length-2;val r=for(i<-0 to l;j<-i to l;c=s(0).substring(i,j+2);if(c==c.reverse)) yield c;println(r.distinct.mkString(" "))}}

Lalith
quelle
Hallo Lalith, ich habe deinen Code ein wenig verkürzt: Kein Leerzeichen vor dem Ausgeben und Erweitern der App, anstatt main, println => print und distinct => toSet zu überschreiben
Benutzer unbekannt
1

Perl 6 ,  35  32 Bytes

{unique m:ex/(.+).?<{$0.flip}>/}

Probier es aus

{set m:ex/(.+).?<{$0.flip}>/}

Probier es aus

Erweitert:

{  # bare block lambda with implicit parameter 「$_」

  set             # turn into a Set object (ignores duplicates)

  \             # stringify 「~」 all of these 「«」 (possibly in parrallel)
                  # otherwise it would be a sequence of Match objects

  m               # match
  :exhaustive     # in every way possible
  /
    ( .+ )        # at least one character 「$0」
    .?            # possibly another character (for odd sized sub-palindromes)
    <{ $0.flip }> # match the reverse of the first grouping
  /
}
Brad Gilbert b2gills
quelle
1

Gelee , 9 Bytes

ẆQŒḂÐfḊÐf

Probieren Sie es online!

Erik der Outgolfer
quelle
Die Ausgabe Ihres Permalinks ist falsch.
Dennis
@Dennis, warum wurde dies ein falsches Ziel, dann> _> behoben
Erik der Outgolfer
7 Bytes mit neuem Jelly.
user202729
1

APL (Dyalog Classic) , 27 Byte

{∪⍵/⍨≡∘⌽¨⍨⍵}∘⊃(,/1↓⍳∘≢,/¨⊂)

Probieren Sie es online!

{∪⍵/⍨≡∘⌽¨⍨⍵}∘⊃(,/1↓⍳∘≢,/¨⊂)    Monadic train:
                                Enclose the input, '12131331'
                     ⍳∘≢          Range from 1 to length of input
                     ⍳∘≢,/¨⊂      List of list of substrings of each length
                   1            Remove the first list (length-1 substrings)
                ,/              Put the rest of the substrings into a single list.
{∪⍵/⍨≡∘⌽¨⍨⍵}                   To the result, apply this function which
                                   keeps all palindromes from a list:
      ≡∘⌽¨⍨⍵                    Boolean value of whether each (¨) string in argument
      ≡∘⌽                      is equal to its own reverse

  ⍵/⍨                           Replicate (filter) argument by those values.
                                 This yields the length >1 palindromes.
                                Remove duplicates from the list of palindromes.
Lirtosiast
quelle
Aufgrund der Aufforderung von OP nach "Code" ist das Snippet ∪w/⍨≡∘⌽¨⍨w←⊃,/1↓(⍳∘≢,/¨⊂)gültig.
Adám
@Adám Ich denke, ich werde diese Antwort behalten, da sie der modernen Website-Standards dient, zumal sie nicht den Gesamtsieg bringt.
Lirtosiast
1

Japt , 14 Bytes

Êò2@ãX fêSÃc â

Probieren Sie es online!

Erläuterung:

Êò2               #Get the range [2...length(input)]
   @      Ã       #For each number in that range:
    ãX            # Get the substrings of the input with that length
       fêS        # Keep only the palindromes
           c      #Flatten
             â    #Keep unique results
Kamil Drakari
quelle
1

PowerShell , 99 Byte

$args|% t*y|%{$s+=$_
0..$n|%{if($n-$_-and($t=-join$s[$_..$n])-eq-join$s[$n..$_]){$t}}
$n++}|sort -u

Probieren Sie es online!

Weniger golfen:

$args|% toCharArray|%{
    $substring+=$_
    0..$n|%{
        if( $n-$_ -and ($temp=-join$substring[$_..$n]) -eq -join$substring[$n..$_] ){
            $temp
        }
    }
    $n++
}|sort -Unique
mazzy
quelle
1

Brachylog , 11 Bytes

{s.l>1∧.↔}ᵘ

Probieren Sie es online!

(Die Kopfzeile im Link ist zum Zeitpunkt der Veröffentlichung unterbrochen. Hier ist also das Vergleichselement (funktionsäquivalent in Brachylog) nur für den ersten Testfall mit einem wam Ende, um die Ausgabe tatsächlich zu drucken.)

               The output is
{        }ᵘ    a list containing every possible unique
 s.            substring of
               the input
   l           the length of which
    >          is greater than
     1         one
      ∧        and
       .       which
        ↔      reversed
               is itself. (implicit output within the inline sub-predicate)

Ich habe das Gefühl, dass es eine kürzere Möglichkeit gibt, um zu überprüfen, ob die Länge größer als 1 ist. (Wenn es keine trivialen Palindrome herausfiltern würde, wäre es einfach {s.↔}ᵘ.)

Nicht verwandte Zeichenfolge
quelle
1

APL (NARS), 65 Zeichen, 130 Byte

{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}

Prüfung:

  r←{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}
  o←⎕fmt
  o r '1234442'
┌2───────────┐
│┌2──┐ ┌3───┐│
││ 44│ │ 444││
│└───┘ └────┘2
└∊───────────┘
  o r '3333'
┌3───────────────────┐
│┌4────┐ ┌3───┐ ┌2──┐│
││ 3333│ │ 333│ │ 33││
│└─────┘ └────┘ └───┘2
└∊───────────────────┘
  o r  "12131331"
┌5─────────────────────────────────┐
│┌4────┐ ┌3───┐ ┌2──┐ ┌3───┐ ┌3───┐│
││ 1331│ │ 121│ │ 33│ │ 313│ │ 131││
│└─────┘ └────┘ └───┘ └────┘ └────┘2
└∊─────────────────────────────────┘
  o r '1234'
┌0─┐
│ 0│
└~─┘


{0=≢m←∪b/⍨{1≥≢⍵:0⋄∧/⍵=⌽⍵}¨b←↑∪/{x[⍵;]⊂y}¨⍳≢x←11 1‼k k⊢k←≢y←⍵:⍬⋄m}
 y←⍵  assign the argument to y (because it has to be used inside other function)
 x←11 1‼k k⊢k←≢y   assign the lenght of y to k, call the function 11 1‼k k
                   that seems here find all partition of 1 2 ..k
 {x[⍵;]⊂y}¨⍳≢      make partition of arg ⍵ using that set x
 ∪/                set union with precedent to each element of partition y (i don't know if this is ok)
 b←↑               get first assign to b
 {1≥≢⍵:0⋄∧/⍵=⌽⍵}¨ for each element of b return 1 only if the argument ⍵ is such that 
                   "∧/⍵=⌽⍵" ⍵ has all subset palindrome, else return 0
 b/⍨               get the elements in b for with {1≥≢⍵:0⋄∧/⍵=⌽⍵} return 1
 m←∪               make the set return without ripetition element, and assign to m
 0=≢               if lenght of m is 0 (void set) than 
 :⍬⋄m              return ⍬ else return m

es weiß jemand besser warum, und kann dies besser erklären, ohne dies alles zu ändern ... Ich bin mir dieses Codes nicht so sicher, möglich, wenn Testbeispiele zahlreicher sind, wird etwas schief gehen ...

RosLuP
quelle
1

Japt , 9 Bytes

ã â fÅfêU

Versuch es

ã â fÅfêU     :Implicit input of string
ã             :Substrings
  â           :Deduplicate
    f         :Filter elements that return truthy
     Å        :  Slice off first character
       f      :Filter elements that return true
        êU    :  Test for palindrome
Zottelig
quelle
0

Java 8, 202 201 199 Bytes

import java.util.*;s->{Set r=new HashSet();String x;for(int l=s.length(),i=0,j;i<l;i++)for(j=i;++j<=l;)if((x=s.substring(i,j)).contains(new StringBuffer(x).reverse())&x.length()>1)r.add(x);return r;}

Probieren Sie es hier aus.

Wenn eine Funktion nicht zulässig ist und ein vollständiges Programm erforderlich ist, sind es stattdessen 256 255 253 Bytes :

import java.util.*;interface M{static void main(String[]a){Set r=new HashSet();String x;for(int l=a[0].length(),i=0,j;i<l;i++)for(j=i;++j<=l;)if((x=a[0].substring(i,j)).contains(new StringBuffer(x).reverse())&x.length()>1)r.add(x);System.out.print(r);}}

Probieren Sie es hier aus.

Erläuterung:

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

s->{                     // Method with String parameter and Set return-type
  Set r=new HashSet();   //  Return-Set
  String t;              //  Temp-String
  for(int l=s.length(),  //  Length of the input-String
          i=0,j;         //  Index-integers (start `i` at 0)
      i<l;i++)           //  Loop (1) from `0` to `l` (exclusive)
    for(j=i;++j<=l;)     //   Inner loop (2) from `i+1` to `l` (inclusive)
      if((t=s.substring(i,j) 
                         //    Set `t` to the substring from `i` to `j` (exclusive)
         ).contains(new StringBuffer(t).reverse())
                         //    If this substring is a palindrome,
         &t.length()>1)  //    and it's length is larger than 1:
        r.add(t);        //     Add the String to the Set
                         //   End of inner loop (2) (implicit / single-line body)
                         //  End of loop (1) (implicit / single-line body)
  return r;              //  Return the result-Set
}                        // End of method
Kevin Cruijssen
quelle
0

JavaScript (ES6), 107 Byte

Gibt ein Set zurück .

s=>new Set((g=(s,r=[...s].reverse().join``)=>s[1]?(r==s?[s]:[]).concat(g(s.slice(1)),g(r.slice(1))):[])(s))

Testfälle

Arnauld
quelle