8
$\begingroup$

Suppose I have the following StringReplace rule

StringReplace[st, {"a" -> "0", "OverBar[a]" -> "1", "b" -> "1", 
  "OverBar[b]" -> "0", "c" -> "0", "OverBar[c]" -> "1"     , 
  "d" -> "0", "OverBar[d]" -> "1", "e" -> "0", "OverBar[e]" -> "1" }]

Given an output string, is there some way to generate all strings which give this output?

For example

bcccc, bcccd, bccde both give the string 10000. Is there some way to find all of these inverses? For short examples, one could calculate by hand but when the string lengths get large and the number of rules get large this would not be effective. It also seems like it would be difficult to automate.

$\endgroup$
  • 1
    $\begingroup$ It is not guaranteed that the number of strings giving the output is finite—for example, when StringReplace[st, {"a" -> ""}] yields "b". $\endgroup$ – Greg Martin Jul 2 at 1:38
8
$\begingroup$
rules = {"a" -> "0", "OverBar[a]" -> "1", "b" -> "1", 
   "OverBar[b]" -> "0", "c" -> "0", "OverBar[c]" -> "1", "d" -> "0", 
   "OverBar[d]" -> "1", "e" -> "0", "OverBar[e]" -> "1"};
str = "10000";

StringReplaceList[#, Reverse /@ rules] & /@ StringPartition[str, 1];
Outer[StringJoin, Sequence@@%] // Flatten;

MemberQ[%, #] & /@ {"bcccc", "bcccd", "bccde"}

{True, True, True}

The number of solutions

Length[%%]

3125

| improve this answer | |
$\endgroup$
4
$\begingroup$

With a large number of replacement rules it would be slow to find all of them, but you could find a sample of them like this:

inverses = Reap[Do[
      Sow[StringReplace["10000", RandomSample[Reverse /@ rules]]]
      , 100]][[-1, 1]] // DeleteDuplicates;

Results:

OverBar[d]dddd
OverBar[c]OverBar[b]OverBar[b]OverBar[b]OverBar[b]
OverBar[c]eeee
OverBar[a]dddd
OverBar[d]eeee
OverBar[a]cccc
OverBar[d]OverBar[b]OverBar[b]OverBar[b]OverBar[b]
OverBar[e]eeee
OverBar[a]OverBar[b]OverBar[b]OverBar[b]OverBar[b]
OverBar[c]dddd
OverBar[a]eeee
OverBar[e]cccc
bdddd
OverBar[d]cccc
OverBar[d]aaaa
OverBar[e]OverBar[b]OverBar[b]OverBar[b]OverBar[b]
OverBar[a]aaaa
OverBar[c]aaaa
OverBar[e]aaaa
bcccc
beeee
baaaa
OverBar[e]dddd

Confirm that they work:

StringReplace[inverses, rules]

(* result: {"10000", "10000", "10000", "10000", "10000", "10000", "10000", 
"10000", "10000", "10000", "10000", "10000", "10000", "10000", 
"10000", "10000", "10000", "10000", "10000", "10000", "10000", 
"10000", "10000", "10000", "10000"} *)
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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