$str = 'foo-bar-hutzel-putzel';
$len = scalar(@arr = $str =~ /-/g);
$max = (2 ** scalar(@arr)) - 1;
$pat = '^' . '([^-]*)-' x scalar(@arr) . '([^-]*)$';

for $i ( 0..$max ) {
  $bits = sprintf("%03b", $i);
  $subs = '';

  for $j ( 0..($len-1) ) {
    $subs .= '$' . ($j+1) . ((($bits >> $j) & 0x1) ? '-' : '');
  }

  $subs .= '$4';

  eval("(\$tmp = '$str') =~ s/$pat/$subs/;");

  printf("$tmp\n");
}