Inverse of StringReplace

Question

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.

Answer 1

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

Answer 2

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"} *)