Я работаю над проблемой системы MIU из главы 2 «Гедель, Эшер, Бах».

Одно из правил гласит

Rule III: If III occurs in one of the strings in your collection, you may make a new string with U in place of III.

Что означает, что строкаMIII может статьMU, но для других, более длинных строк может быть несколько возможностей [совпадений в скобках]:

MIIII может датьM[III]I >>MUIMI[III] >>MIUMUIIIUIIIU может датьMU[III]UIIIU >>MUUUIIIUMUIIIU[III]U >>MUIIIUUUMUIIIIU может датьMU[III]IU >>MUUIUMUI[III]U >>MUIUU

Четко регулярные выражения, такие как/(.*)III(.*)/ полезны, но я не могу заставить их генерировать каждое возможное совпадение, только первое, которое он находит.

Есть ли способ генерировать все возможные совпадения?

(Обратите внимание, я могу придумать способы сделать это полностью вручную, но я надеюсь, что есть лучший способ, используя встроенные инструменты, регулярные выражения или другие)

(Отредактировано для уточнения дублирующих потребностей.)