# 解題

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.

``````
#!/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
``````

This page contains a single entry by gugod published on July 13, 2010 11:22 AM.

Find recent content on the main index or look in the archives to find all content.