开发者

string validation in Mathematica

I have a string validation function that I want to optimize. The string is of length 2n and composed of 0 and 1's, for example, str="100001". I want to test:

1) whether the number (has to be not less than 1) of 1's in oddly indexded positions in the string is equal to that in the evenly indexed positions

2) whether for every StringTake[str,2*i], i runs from 1 to n-1,开发者_如何学Python the number of 1's in oddly indexded positions in the string is not equal to that in the evenly indexed positions.

In sum, I want to test whether the position 2n is the first time the number of 1's in oddly indexded positions in the string is equal to that in the evenly indexed positions.

"100001" and 101101 is a good string, but not 100100, 100000 nor 000000.

Many thanks.


This code does not test for invalid strings (characters not "0" or "1", length not even).

goodString[str_String] := Module[
  {digits, cumdiffs, pos},
  digits = Transpose[Partition[
    IntegerDigits[ToExpression[str], 10, StringLength[str]], 2]];
  cumdiffs = Subtract @@ Accumulate /@ digits;
  pos = Position[cumdiffs, 0, 1, 1];
  Length[pos] == 1 && pos[[1, 1]] == Length[cumdiffs]
]

Your examples:

goodString /@ {"100001" , "101101", "100100", "100000", "000000"}

Out[302]= {True, True, False, False, False}

There might be faster ways e.g. with NestList. Also if speed is a big issue and strings are likely to be long, you could split out the IntegerDigits[ToExpression[...]] in preprocessing and use Compile on the rest.

Daniel Lichtblau Wolfram Research


(Apologies for the schoolboy-code, this is my first effort with Strings in Mathematica, so I left in my thinking-as-I-went and also some commented-out debug/tracing values)

charcountsvec[s_String, c_String] := Table[
   If[StringTake[s, {i, i}] == c, 1, 0]
   , {i, 1, StringLength[s]}
];

oddchars[s_String] := StringTake[s, {1, -1, 2}]; (*pick out odd chars*)    
evenchars[s_String] := StringTake[s, {2, -1, 2}];

validatestr[str_String] :=     
 Block[{evencounts, oddcounts, answer1, answer2 (*, odds, evens*)},
  evencounts = Accumulate@charcountsvec[(*evens=*)evenchars[str], "1"];
  oddcounts = Accumulate@charcountsvec[(*odds=*)oddchars[str], "1"];
  (*my interpretation of "number of 1's in odd positions the same as in even positions"*)      
  answer1 = Last[oddcounts] == Last[evencounts]; 
  (*my interpretation of "for every..string...whether number of 1's in even/odd positions is not equal"*)      
  answer2 = Fold[And, True, 
    MapThread[Unequal, {Most[oddcounts], Most[evencounts]}]];

  {str, And[answer1, answer2](*,odds,evens,oddcounts,evencounts,answer1,answer2*)}
  ];

Testing:

validatestr/@{"100001","101101","100100","100000","000000"}

{{"100001", True}, {"101101", True}, {"100100", False}, {"100000", False}, {"000000", False}}

validatestr["0000001"](*odd length string pukes, and returns False*)

During evaluation of (Local) In[428]:= MapThread::mptc: Incompatible dimensions of objects at positions {2, 1} and {2, 2} of MapThread[Unequal,{{0,0,0},{0,0}}]; dimensions are {3} and {2}. >>

(Local) Out[432]= {"0000001", False}

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜