Trouver des «sous-palindromes».

24

Le code le plus court qui trouve tous les "sous-palindromes" uniques d'une chaîne, c'est-à-dire: toute sous-chaîne de longueur> 1 qui est un palindrome.

eg.1

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

eg.2

input: "3333"
output: "33", "333", "3333"
Eelvex
la source
1
Une chaîne peut-elle être son propre sous-palindrome? Puisqu'une chaîne est sa propre sous-chaîne.
JPvdMerwe
@JPvdMerwe: Oui, bien sûr.
Eelvex
En fait, plus important encore: quel doit être le résultat 333? Naïvement, vous 33
finiriez
@JPvdMerwe: '333' -> '33', '333'. Je vais modifier la question en conséquence. Merci.
Eelvex
Comment la sortie est-elle spécifiée? Délimité par des virgules avec des guillemets autour de chaque sous-palindrome comme vous le démontrez ici? Un sous-p par ligne?
Joey

Réponses:

11

J, 24 31 40

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

Exemple d'utilisation:

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

Prenez ça, GolfScript!

JB
la source
Admettez-le, vous venez de mettre une décharge d' /dev/randomici pour nous tromper ;-)
Joey
@Joey, essayez par vous-même; p (TBH, je ne pensais pas que cela pouvait fonctionner non plus au début)
JB
Je suis presque sûr que c'est du vrai code. J'ai passé un week-end à essayer d'enrouler ma tête autour de J, mais j'ai échoué lamentablement. Pourtant, je reconnais le code; Je ne comprends tout simplement pas ce que ça fait ;-)
Joey
2
Ne peut-on pas le raccourcir à ~.(#~(1<#*]-:|.)&>),<\\.(24 caractères)?
ephemient
@ephemient C'est vrai. (On dirait que j'étais coincé dans l'état d'esprit "la réponse doit être une fonction", qui ne s'applique pas ici.) Modifié, merci!
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
la source
5

Haskell 98, 88 91 96

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

Python - 138 136

Ce code ne duplique pas les sous-palindromes.

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
la source
1
Passez '"'+t+'"'à tpour économiser de l'espace, bien qu'il utilise des guillemets simples.
Thomas O
3

Ruby - 126 102 97 caractères

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
la source
3

Golfscript, 48 caractères

subpalindrome.gs

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

Usage:

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

La première opération {,}{(;}/transforme une chaîne en une liste de sous-chaînes de fin. Une transformation de sous-chaînes de tête similaire est ensuite mappée sur le résultat. Aplatissez ensuite avec {+}*, filtrez les palindromes en utilisant le prédicat .,1>\.-1%=*, saisissez des valeurs uniques avec .&, puis imprimez.

Il serait plus simple d'extraire la transformation des sous-chaînes de fin en tant que bloc et de la réutiliser en remplacement des sous-chaînes de tête après avoir inversé chaque sous-chaîne de fin, mais je ne peux pas trouver de façon succincte de le faire.

roobs
la source
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
la source
Remplacez main=getLine>>=(\x->putStrLn$intercalate", "$toList$p x)par main=getLine>>=putStrLn.intercalate", ".toList.p. Je substituerais également un appel à pson corps.
Yasir Arsanukaev, le
Sous-chaînes / = subsequences! Votre programme signale plus de sous-index que la sortie de référence pour l'exemple 1. ("1111" par exemple)
JB
2

J, 48

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

par exemple

~.(#~10&<)((]h-:"0&f|.h)#[:f]h) '12131331'
121 131 313 1331 33
Eelvex
la source
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).

Exemple d'utilisation:

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

?- p("3333",R).
R = ['33', '333', '3333'].
JB
la source
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]}

Cela attend l'entrée sur stdin et lancera tous les palindromes trouvés un par ligne sur stdout:

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

(Lorsqu'il est exécuté, cmdil devient echo 12131331|powershell -file subp.ps1- c'est juste que cela $inputprend une signification légèrement différente selon la façon dont le script a été appelé, mais il peut être stdin, mais pas de manière interactive.)

2011-01-30 13:57 (111) - Première tentative.

2011-01-30 13:59 (109) - Déclaration de variable en ligne.

2011-06-02 13:18 (104) - Recherche de sous-chaîne refaite en joignant un tableau de caractères au lieu d'appeler .Substring()et en ligne un peu plus.

Joey
la source
2

Q, 78

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

usage

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
la source
2

Rétine , 34 27 octets

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

Essayez-le en ligne!

La suite de tests a besoin d'un Mcar elle est suivie d'une autre étape pour insérer des lignes vides entre les cas de test.

Explication

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

Print ( !) toutes les correspondances uniques ( @) et superposées ( &) de l'expression régulière (.)+.?(?<-1>\1)+(?(1)^). Cela correspond à un palindrome de longueur 2 ou plus utilisant des groupes d'équilibrage. Il y a une mise en garde à la partie "tous les matchs qui se chevauchent": nous pouvons obtenir au plus un match par position de départ. Cependant, si deux palindromes de longueur différente commencent à la même position, le palindrome le plus court réapparaîtra à la fin du palindrome le plus long. Et comme l'avidité de +prioriser les matchs plus longs, nous obtenons tous les palindromes de toute façon.

Martin Ender
la source
2

05AB1E , 11 10 octets

ŒÙʒÂQ}žQSK

Essayez-le en ligne!

Urne de poulpe magique
la source
1
9 octets
scottinet
@scottinet échoue pour les célibataires, EG1234142141410010101000
Magic Octopus Urn
1
Le vôtre aussi, mais pas de la même manière. o_O Il se passe quelque chose qui nécessite une enquête. En attendant, voici une version de 10 octets qui semble fonctionner
scottinet
Il y avait un bug avec uniquify, je l'ai corrigé. Maintenant, votre réponse de 11 octets et mes 9 octets fonctionnent :-)
scottinet
@scottinet Votre 10 octets peut également être un 9 octets en passant 1›à . :)
Kevin Cruijssen
1

Perl, 112

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

JavaScript (ES6), 120 octets

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}

Cette fonction prend une chaîne en entrée et génère un tableau.

Luc
la source
1

Clojure, 81 octets

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

for était un match parfait ici :) Pourrait utiliser :when(=(reverse p)p) si l'entrée était une liste de caractères OU une chaîne complète ne comptait pas comme un palindrome, en fait dans ce cas, la plage maximale de ipourrait l'être (count %)également.

Boîtier le plus compact pour référence:

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

Python, 83 102 caractères

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

La phrase (t[1:]or())and... équivaut (...)if t[1:]else()et enregistre un caractère! Je suis extrêmement fier de cela, compte tenu des économies.

Exemple:

python x
"51112232211161"
set(['11', '22', '11122322111', '161', '111', '112232211', '1223221', '22322', '232'])
boothby
la source
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(" "))}

Pour garder cela une comparaison de pommes à pommes avec l'autre réponse de Scala, j'ai également fait du mien un objet qui étend l'application. Plutôt que d'itérer la chaîne d'entrée manuellement et d'utiliser la sous-chaîne, j'ai utilisé la fonction slide () pour créer une séquence de toutes les sous-chaînes pour moi.

bkuder
la source
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
la source
Salut Lalith, j'ai raccourci un peu votre code: pas de blanc avant le rendement et l'extension de l'application au lieu d'écraser main, println => print et distinct => toSet
utilisateur inconnu
1

Perl 6 ,  35  32 octets

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

Essaye-le

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

Essaye-le

Étendu:

{  # 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
la source
1

Gelée , 9 octets

ẆQŒḂÐfḊÐf

Essayez-le en ligne!

Erik le Outgolfer
la source
La sortie de votre permalien est incorrecte.
Dennis
@Dennis pourquoi cela est-il devenu une cible dupe alors> _> fixe
Erik l'Outgolfer
7 octets avec une nouvelle gelée.
user202729
1

APL (Dyalog Classic) , 27 octets

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

Essayez-le en ligne!

{∪⍵/⍨≡∘⌽¨⍨⍵}∘⊃(,/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
la source
En raison de l'OP appelant "code", l'extrait ∪w/⍨≡∘⌽¨⍨w←⊃,/1↓(⍳∘≢,/¨⊂)est valide.
9h11
@ Adám Je pense que je vais garder cette réponse car elle est dans l'intérêt des standards du site moderne, d'autant plus qu'elle n'obtient pas la victoire globale.
lirtosiast
1

Japt , 14 octets

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

Essayez-le en ligne!

Explication:

Êò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
la source
1

PowerShell , 99 octets

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

Essayez-le en ligne!

Moins golfé:

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

Brachylog , 11 octets

{s.l>1∧.↔}ᵘ

Essayez-le en ligne!

(L'en-tête du lien est cassé au moment de la publication, alors voici le prédicat (équivalent de la fonction dans Brachylog) uniquement sur le premier cas de test, avec un wà la fin pour réellement imprimer la sortie.)

               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)

J'ai l'impression qu'il existe un moyen plus court de vérifier que la longueur est supérieure à 1. (Si cela ne filtrait pas les palindromes triviaux, ce serait juste {s.↔}ᵘ.)

Chaîne indépendante
la source
1

APL (NARS), 65 caractères, 130 octets

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

tester:

  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

si quelqu'un sait mieux pourquoi, et peut l'expliquer mieux, sans changer tout cela ... Je ne suis pas si certain de ce code, possible si les exemples de test sont plus nombreux, quelque chose va mal tourner ...

RosLuP
la source
1

Japt , 9 octets

ã â fÅfêU

Essayez-le

ã â 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
Hirsute
la source
0

Java 8, 202 201 199 octets

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

Essayez-le ici.

Si une fonction n'est pas autorisée et qu'un programme complet est requis, c'est 256 255 253 octets à la place:

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

Essayez-le ici.

Explication:

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
la source
0

JavaScript (ES6), 107 octets

Renvoie un ensemble .

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

Cas de test

Arnauld
la source