Finding "sub-palindromes" 2: subsequences.

The same task as Finding "sub-palindromes" but instead of finding substrings you must find subsequences that are not substrings.

eg1:

input: "12131331"
output: 
"11", "33", "111", "121", "131", "313", "333", "1111", "1331", "11311", "13331"
or 
"11", "33", "111", "333", "1111", "11311", "13331"

eg2:

input: "3333"
output: 
"33", "333"
or
(null)

Input is a string of printable ascii characters.
Output is a list of unique strings.
If a subsequence also appears as a substring it may be omitted.
Shortest code wins.

Eelvex

Posted 2011-02-11T20:06:33.507

Reputation: 5 204

It may be omitted or it must be omitted? Header and details don't match. – J B – 2011-02-11T23:29:40.033

@J B: may be omitted. Where is the mismatch? – Eelvex – 2011-02-11T23:34:43.497

@Eelvex "subsequences that are not substrings". That part reads like substrings aren't allowed. – J B – 2011-02-11T23:53:30.137

@J-B: Substrings are not allowed. What you may or may not omit is a subsequence that also appears as a substring. Take a look at the examples: "1331" is a subsequence "12 13 13 31 " but also a substring "1213 1331 " so you may omit it. – Eelvex – 2011-02-12T00:09:07.643

1@Eelvex: look at it this way. The example output includes "1331". But "1331" is a substring. Thus I don't understand why it's there, given that substrings are not allowed. – J B – 2011-02-12T11:12:00.207

@J-B: Look at it this way: use sequence indexes instead of values. The sequence I'm referring to is "2367" while the sequence you are referring to is "4567". They are completely different but happen to have the same value so you may omit the sequence if it is easier to code it that way. – Eelvex – 2011-02-12T11:35:20.840

@J-B: When I say "subsequences that are not substrings" I mean the set of subsequences that does not include the subset of substrings. i.e. the relative complement of subsequences to substrings. I think the misunderstanding is that it might seem I mean the list of subsequences that is not common with the list of substrings. – Eelvex – 2011-02-12T11:40:44.050

@J-B: btw, you'are not allowed to print "3333" in the second example because there is no such subsequence; only a substring. – Eelvex – 2011-02-12T11:42:58.010

Answers

GolfScript, 39 characters

:^1/[""]\{`{1$\+}+%}/.&{..-1%=^@?0<&},`

Examples:

> "12131331"
["11" "333" "111" "13331" "13131" "1111" "11311"]

> "3333"
[]

Basic blocks of the code:

# Save input in variable
:^

# Build all possible subsequences of the input
1/[""]\{`{1$\+}+%}/

# Filter unique ones
.&

# Filter relevant palindromes
{.
  .-1%=   # check if palindrome
  ^@?0<   # check if sequence is no substring
  &       # and operation on both
},

# Format output
`

Howard

Posted 2011-02-11T20:06:33.507

Reputation: 23 109

Haskell (119)

import Data.List
main=interact f
f a=show.nub.filter(\x->(not$isInfixOf a x)&&x==reverse x&&length x>1)$subsequences a

Isn't too difficult with a builtin subsequences and nub... :)

FUZxxl

Posted 2011-02-11T20:06:33.507

Reputation: 9 656

Golfscript (95)

);.{{(\a\:x;.{[x]\+}%+}:b;{.!{[$]}{b}if}:a;.a{..-1%=&},\{,}{(;}/{{,}{);}/}%{+}*-.&{`}%", "*}and

I haven't really tried to golf this further, it's just a combination of left overs.

The question is inconsistent. My program prints all palindromic subsequences that are not substrings. Hope this is OK.

Example 1:

echo "12131331" | ruby golfscript.rb subseq_not_substr.gs
"11", "111", "13331", "13131", "1111", "11311"

Example 2:

echo "3333" | ruby golfscript.rb subseq_not_substr.gs

Empty String Example:

echo "" | ruby golfscript.rb subseq_not_substr.gs

With uglier output formatting, eg [11 111 13331 13131 1111 11311], it could be made a bit shorter.

roobs

Posted 2011-02-11T20:06:33.507

Reputation: 299

Any way of formatting the output list is ok. Make it shorter :) – Eelvex – 2011-02-12T10:47:25.453