Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

There are a long list of strings $s$ and two lists of substrings $s1$ and $s2$. I want to take all elements of $s$ which contain a substring from $s2$ and such that before it on no more than $n$ places there is a string containing a substring from $s1$. For example, if

s={"a","b1","c","b2","a","c","b3"};
s1={"a"} ;
s2={"b"};
n=2;

the result should be {"b1","b3"} because two previous to "b2" elements don't contain substring "a".

It can be done with the help of Position, creating and comparing two lists of elements positions with fragments from $s1$ and $s2$. Is there a more direct way without creating additional lists?

share|improve this question
1  
I note that each of the three methods posted produce different results. I don't know which if any is correct. –  Mr.Wizard Jul 22 '12 at 11:21
1  
I want to take another crack at this. Please clarify: is a string containing both "a" and "b" to automatically be returned? –  Mr.Wizard Jul 22 '12 at 14:03
    
Yes, all strings containing "b" to be returned. –  Andrew Jul 22 '12 at 14:49
    
Andrew, certainly you don't mean any string anywhere containing "b" is to be returned, so I'm still not clear on that. Please see my second answer and tell me which (if either) behavior is as you want. –  Mr.Wizard Jul 22 '12 at 14:52
    
You mean "such that in it's n previous positions there is at least one string containing a substring of s1"? –  Rojo Jul 22 '12 at 22:29
show 1 more comment

5 Answers

up vote 2 down vote accepted

Second attempt, working on the assumption that "axb" should not be returned:

s = {"a", "b1", "c", "b2", "a", "c", "b3", "axb"};
s1 = {"a"};
s2 = {"b"};
n = 2;

f = (If[# > 0 && ! StringFreeQ[#2, s2], Sow@#2]; 
     If[! StringFreeQ[#2, s1], n, # - 1]) &;

Reap[Fold[f, 0, s]][[2, 1]]
{"b1", "b3"}

If "axb" should be returned, then:

f = (If[! StringFreeQ[#, s1], i = n, --i]; 
     If[i >= 0 && ! StringFreeQ[#, s2], Sow@#]) &;

Reap[i = 0; Scan[f, s]][[2, 1]]
{"b1", "b3", "axb"}

Since this answer was Accepted I guess I'm on the right path. I shall provide an additional method designed for speed using ListCorrelate (inspired by R.M's answer) and Pick.

bin = 1 - Boole@StringFreeQ[s, #] &;

Pick[
  s,
  bin[s2] ListCorrelate[ConstantArray[1, n + 1], bin[s1], n + 1, 0] // Unitize,
  1
]
{"b1", "b3", "axb"}

If you want the behavior that does not return "axb" use ConstantArray[1, n].

share|improve this answer
    
@R.M I think I should combine the answers and include performance testing as they exchange places depending on the data. Now is not the time however. Poke me if I don't get back to it in 24 hours. –  Mr.Wizard Jul 22 '12 at 16:14
add comment

This is probably similar to what you alluded to in the question but perhaps it is helpful anyway:

s = {"a", "b1", "c", "b2", "a", "c", "b3", "axb"};
s1 = {"a"};
s2 = {"b"};
n = 2;

Cases[
  s[[Max[1, # - n] ;; #]] & @@@ Position[StringFreeQ[s, s2], False],
  {x__, b_} /; ! StringFreeQ["" <> x, s1] :> b
]
{"b1", "b3"}

If it is desired to return "axb" in the example above use StringFreeQ[x <> b, s1]

share|improve this answer
1  
thanks, it work correctly if for "b" on a segment [#,#+n] there is only one element with "a". Otherwise there will be multiple copies of the same string in the result. –  Andrew Jul 22 '12 at 13:23
    
@Andrew You're right of course. I'm sorry but I don't have time to fix this now. –  Mr.Wizard Jul 22 '12 at 13:53
    
@Andrew I have revised this answer to address the problem. Please let me know if it works. I still do not know if you want to return e.g. "axb" automatically. –  Mr.Wizard Jul 22 '12 at 14:37
add comment

I'm not sure if this counts as "creating additional lists", but it seems to work:

With[{s = {"a", "b1", "c", "b2", "a", "c", "b3"}, s1 = {"a"}, s2 = {"b"}, n = 2},
 Last /@ Select[Partition[s, n + 1, 1, {-1, -1}, {}],
                ! (StringFreeQ[Last[#], s2] || And @@ StringFreeQ[Most[#], s1]) &]]
share|improve this answer
    
thanks for the idea. It doesn't work for $n\ne2$, but probably it can be mended just changing Partition options. –  Andrew Jul 22 '12 at 13:16
    
Could you give an example of a case where this construction doesn't work? I have a possible tweak in mind, but I'd like to be sure if it'll work in those cases you mention... –  J. M. Jul 22 '12 at 14:06
    
It gives "b3" for $n=3$ in this example and for $n=1$ produces an error message. –  Andrew Jul 22 '12 at 14:52
    
Try the current version now. –  J. M. Jul 22 '12 at 14:54
add comment

Here's a solution using ListCorrelate:

test[list_, pat1_, pat2_] /; ! StringFreeQ[Last@list, pat1] := 
    Last@list /; ! StringFreeQ[StringJoin@Most@list, pat2]
test[_, _, _] := ## &[]

ListCorrelate[ConstantArray[1, n + 1], s, {-1, -1}, {""}, ##2 &, test[{##}, s2, s1] &] 
(* {"b1", "b3"} *)
share|improve this answer
add comment

How about this:

ReplaceList[s,{___,p:Repeated[_,n]/;!StringFreeQ[StringJoin@p,s1],x_/;!StringFreeQ[x,s2],___}:>x]
share|improve this answer
    
Thanks. It could give repeated strings in the answer. –  Andrew Jul 22 '12 at 13:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.