Encontrar "sub-palíndromos".

24

El código más corto que encuentra todos los "sub-palíndromos" únicos de una cadena, es decir: cualquier subcadena con longitud> 1 que es un palíndromo.

eg.1

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

eg.2

input: "3333"
output: "33", "333", "3333"
Eelvex
fuente
1
¿Puede una cadena ser su propio sub-palíndromo? Como una cadena es su propia subcadena.
JPvdMerwe
@JPvdMerwe: Sí, por supuesto.
Eelvex
En realidad, lo más importante: ¿cuál debe ser la salida de 333ser? Ingenuamente terminarías imprimiendo 33dos veces
JPvdMerwe
@JPvdMerwe: '333' -> '33', '333'. Editaré la pregunta en consecuencia. Gracias.
Eelvex
¿Cómo se especifica la salida? Delimitado por comas con comillas, ¿se encuentra en cada sub-palíndromo como lo demuestra aquí? ¿Una subp por línea?
Joey

Respuestas:

11

J, 24 31 40

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

Uso de la muestra:

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

¡Toma eso, GolfScript!

JB
fuente
Admítelo, acabas de poner un vertedero /dev/randompara engañarnos ;-)
Joey
@Joey pruébalo por ti mismo; p (TBH, tampoco creía que pudiera funcionar al principio)
JB
Estoy bastante seguro de que es el código real. Pasé un fin de semana tratando de entender a J, pero fracasé miserablemente. Aún así, reconozco el código; Simplemente no entiendo lo que hace ;-)
Joey
2
¿No se puede acortar a ~.(#~(1<#*]-:|.)&>),<\\.(24 caracteres)?
Ephemient
@ephemient Lo hace de hecho. (Parece que estaba atrapado en la mentalidad de "la respuesta debe ser una función", que no se aplica aquí.) Editado, ¡gracias!
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
fuente
5

Haskell 98, 88 91 96

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

Python - 138 136

Este código no duplica los sub-palíndromos.

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
fuente
1
Cambie '"'+t+'"'a tpara ahorrar algo de espacio, aunque utiliza comillas simples.
Thomas O
3

Ruby - 126102 97 caracteres

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
fuente
3

Golfscript, 48 caracteres

subpalindrome.gs

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

Uso:

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

La primera operación {,}{(;}/convierte una cadena en una lista de subcadenas finales. Luego se asigna una transformación similar de subcadenas iniciales sobre el resultado. Luego aplanar con {+}*, filtrar palíndromos usando el predicado .,1>\.-1%=*, tomar valores únicos con .&, luego imprimir bonito.

Sería mejor extraer la transformación de las subcadenas finales como un bloque y reutilizarla como reemplazo de las subcadenas iniciales después de invertir cada subcadena posterior, pero no puedo encontrar una manera sucinta de hacerlo.

roobs
fuente
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
fuente
Reemplazar main=getLine>>=(\x->putStrLn$intercalate", "$toList$p x)con main=getLine>>=putStrLn.intercalate", ".toList.p. También sustituiría una llamada a pcon su cuerpo.
Yasir Arsanukaev 01 de
Subcadenas / = subsequences! Su programa informa más subpalíndromes que la salida de referencia, por ejemplo 1. ("1111" por ejemplo)
JB
2

J, 48

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

p.ej

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

Uso de la muestra:

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

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

Esto espera la entrada en stdin y arrojará todos los palíndromos encontrados uno por línea en stdout:

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

(Cuando se ejecuta desde que cmdse convierte echo 12131331|powershell -file subp.ps1, es solo que $inputtiene un significado ligeramente diferente dependiendo de cómo se llamó el script, pero puede ser estándar, solo que no de forma interactiva).

30-01-2011 13:57 (111) - Primer intento.

2011-01-30 13:59 (109) - Declaración de variable en línea.

2011-06-02 13:18 (104) - Se rehizo el hallazgo de la subcadena uniéndose a una matriz de caracteres en lugar de llamar .Substring()e insertado un poco más.

Joey
fuente
2

Q, 78

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

uso

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
fuente
2

Retina , 34 27 bytes

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

Pruébalo en línea!

El conjunto de pruebas necesita un Mporque es seguido por otra etapa para insertar líneas vacías entre los casos de prueba.

Explicación

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

Imprime ( !) todas las @coincidencias únicas ( ), superpuestas ( &) de la expresión regular (.)+.?(?<-1>\1)+(?(1)^). Esto coincide con un palíndromo de longitud 2 o más utilizando grupos de equilibrio. Hay una advertencia para la parte de "todas las coincidencias superpuestas": podemos obtener como máximo una coincidencia por posición inicial. Sin embargo, si dos palíndromos de diferente longitud comienzan en la misma posición, el palíndromo más corto aparecerá nuevamente al final del palíndromo más largo. Y dado que la codicia de las +prioridades da lugar a partidos más largos, de todos modos estamos obteniendo palíndromos.

Martin Ender
fuente
2

05AB1E , 11 10 bytes

ŒÙʒÂQ}žQSK

Pruébalo en línea!

Urna de pulpo mágico
fuente
1
9 bytes
scottinet
@scottinet falla para solteros, EG1234142141410010101000
Urna de pulpo mágica
1
La suya también, pero no de la misma manera. o_O Está sucediendo algo que necesita investigación. Mientras tanto, aquí hay una versión de 10 bytes que parece funcionar
scottinet el
Hubo un error con uniquify, lo arreglé. Ahora tanto su respuesta de 11 bytes como mis 9 bytes funcionan :-)
scottinet
@scottinet Su 10-byter también puede ser un 9-byter cambiando 1›a . :)
Kevin Cruijssen
1

Perl, 112

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

JavaScript (ES6), 120 bytes

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}

Esta función toma una cadena como entrada y genera una matriz.

Luke
fuente
1

Clojure, 81 bytes

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

forera una combinación perfecta aquí :) Podría usarse :when(=(reverse p)p)si la entrada fuera una lista de caracteres O una cadena completa no cuenta como un palíndromo, en ese caso, el rango máximo de ipodría ser (count %)también.

El estuche más compacto para referencia:

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

Python, 83 102 caracteres

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

La frase (t[1:]or())and...es equivalente a(...)if t[1:]else() y guarda un personaje! Estoy demasiado orgulloso de esto, dados los ahorros.

Ejemplo:

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

Para mantener esta comparación de manzanas con manzanas con la otra respuesta de Scala, también hice del mío un objeto que extiende la aplicación. En lugar de iterar la cadena de entrada manualmente y usar la subcadena, aproveché el desplazamiento () para crear una secuencia de todas las subcadenas para mí.

bkuder
fuente
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
fuente
Hola Lalith, acorté un poco tu código: sin espacios en blanco antes de ceder y extender la aplicación en lugar de sobrescribir main, println => print y distinct => toSet
usuario desconocido
1

Perl 6 ,  35  32 bytes

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

Pruébalo

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

Pruébalo

Expandido:

{  # 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
fuente
1

Jalea , 9 bytes

ẆQŒḂÐfḊÐf

Pruébalo en línea!

Erik el Outgolfer
fuente
La salida de su enlace permanente es incorrecta.
Dennis
@Dennis, ¿por qué esto se convirtió en un objetivo de engaño?> _>
Arreglado
7 bytes con nueva gelatina.
user202729
1

APL (Dyalog Classic) , 27 bytes

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

Pruébalo en línea!

{∪⍵/⍨≡∘⌽¨⍨⍵}∘⊃(,/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
fuente
Debido a que OP solicita "código", el fragmento ∪w/⍨≡∘⌽¨⍨w←⊃,/1↓(⍳∘≢,/¨⊂)es válido.
Adám
@ Adám Creo que mantendré esta respuesta ya que es por el bien de los estándares modernos del sitio, especialmente porque no obtiene la victoria general.
lirtosiast
1

Japt , 14 bytes

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

Pruébalo en línea!

Explicación:

Êò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
fuente
1

PowerShell , 99 bytes

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

Pruébalo en línea!

Menos golfizado:

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

Brachylog , 11 bytes

{s.l>1∧.↔}ᵘ

Pruébalo en línea!

(El encabezado en el enlace está roto en el momento de la publicación, así que aquí está el predicado (equivalente de función en Brachylog) solo en el primer caso de prueba, con un wal final para imprimir realmente el resultado).

               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)

Siento que hay una forma más corta de verificar que la longitud es mayor que 1. (Si no filtrara los palíndromos triviales, simplemente sería {s.↔}ᵘ).

Cadena no relacionada
fuente
1

APL (NARS), 65 caracteres, 130 bytes

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

prueba:

  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

Alguien sabe mejor por qué, y puede explicar esto mejor, sin cambiar todo esto ... No estoy tan seguro de este código, posible si los ejemplos de prueba son más numerosos, algo saldrá mal ...

RosLuP
fuente
1

Japt , 9 bytes

ã â fÅfêU

Intentalo

ã â 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
Lanudo
fuente
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;}

Pruébalo aquí

Si una función no está permitida y se requiere un programa completo, son 256 255 253 bytes en su lugar:

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

Pruébalo aquí

Explicación:

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
fuente
0

JavaScript (ES6), 107 bytes

Devuelve un conjunto .

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

Casos de prueba

Arnauld
fuente