解題

在 Perl 社群的 Blog 上看到 這個問題:

Consider a word (well, invented one): noogoo. Now, consider you want to do all possible combinations substituting oo with aa, that is, generate naagoo and noogaa.

也就是說，寫個函式，讓它吃三個字串輸入: s, x, y。並使其傳回一集合，內容是：將 s 中各處出現的 x 代換為 y 的組合。有字串代換，有排列組合，是個有意思的題目。

想了個遞迴解：

#!/usr/bin/env perl
use 5.010;

# Combinatory Substitution Generator
# cs(s, x, y) #=> ()
#   := s, if x is not in s
#   := cs(s', x, y) + map { sp + $_ } cs(sx, x, y), otherwise
#        where s' = s with the first occurence of x replaced with y
#              sp = substring of s from the beginning to the first character of first occurence of x
#              sx = s with sp removed
sub cs {
    my ($s, $x, $y) = @_;
    return $s if index($s, $x) < 0;

    my $pivot_pos = index($s, $x) + 1;
    my $sp = substr($s, 0, $pivot_pos);
    my $sx = substr($s, $pivot_pos);

    substr($s, index($s, $x), length($x)) = $y;
    return cs($s, $x, $y), map { $sp . $_ } cs($sx, $x, $y);
}

say for cs("lady gaga", "ga", "gu");

輸出如:

lady gugu
lady guga
lady gagu
lady gaga

偶爾需要像這樣小小練習預防老年痴呆啊...