递归/穷举地将点插入字符串

Question

我想在任何输入字符串中插入点。

例如，输入anystr，并输出所有可能性

a.nystr
an.ystr
any.str
anys.tr
anyst.r
a.n.ystr
a.ny.str
a.nys.tr
a.nyst.r
an.y.str
an.ys.tr
an.yst.r
......
anys.t.r
a.n.y.str
a.n.ys.tr
......
......
a.n.y.s.t.r

很容易插入一个点

a=anystr

for i in `seq 1 $((${#a}-1))`; do
    echo "${a:0:$i}.${a:$i}"
done

但是，如何对不同长度的输入字符串的所有可能性进行循环？

Answer 1

使用POSIX sh：

dot() {
  dot_helper()
    case $2 in
    '') printf '%s\n' "$1" ;;
     *) dot_helper "$1" "${2#?}"
        dot_helper "${1%"$2"}.$2" "${2#?}"
    esac

  case $1 in
  '') ;;
   *) dot_helper "$1" "${1#?}"
  esac
}

$ dot anystr
anystr
anyst.r
anys.tr
anys.t.r
any.str
any.st.r
any.s.tr
...
a.n.y.s.t.r

Answer 2

以下是使用我在评论中提出的二进制设计思想的实现：

value="anystr"
len=$(( ${#value} - 1 ))
combos=$( bc <<< "2^($len)-1" )
count=0
periods=('' '.')
while [[ count -le  $combos ]]
do
  # Convert to binary - see https://stackoverflow.com/a/10278539/2203038
  binary_count=$( dc -e "$count 2op")
  # add leading 0's and a single trailing 0 (we never put a . after the last letter)
  binary_count=$( printf "%0${len}d" $binary_count )
  
  # loop through the binary_count and value - spitting out a letter and a '.' or ''
  result=''
  x=0
  while [[ x -le ${#value} ]]
  do
    result="$result${value:$x:1}${periods[${binary_count:$x:1}]}"
    x=$(( x + 1 ))
  done
  echo "$count: $binary_count $result"

 count=$(( count + 1 )) 

done

以下是结果：

0: 00000 anystr
1: 00001 anyst.r
2: 00010 anys.tr
3: 00011 anys.t.r
4: 00100 any.str
5: 00101 any.st.r
6: 00110 any.s.tr
7: 00111 any.s.t.r
8: 01000 an.ystr
9: 01001 an.yst.r
10: 01010 an.ys.tr
11: 01011 an.ys.t.r
12: 01100 an.y.str
13: 01101 an.y.st.r
14: 01110 an.y.s.tr
15: 01111 an.y.s.t.r
16: 10000 a.nystr
17: 10001 a.nyst.r
18: 10010 a.nys.tr
19: 10011 a.nys.t.r
20: 10100 a.ny.str
21: 10101 a.ny.st.r
22: 10110 a.ny.s.tr
23: 10111 a.ny.s.t.r
24: 11000 a.n.ystr
25: 11001 a.n.yst.r
26: 11010 a.n.ys.tr
27: 11011 a.n.ys.t.r
28: 11100 a.n.y.str
29: 11101 a.n.y.st.r
30: 11110 a.n.y.s.tr
31: 11111 a.n.y.s.t.r

我最近从bash改为python作为我的首选语言。所以我也倾向于在python中尝试：

value="anystr"
for x in range(2**(len(value)-1)):
  binary_value = x 
  for c in range(len(value)):
    print(value[c],end='')
    if binary_value & 1:
      print('.', end='')
    binary_value >>= 1
  print()

基于python实现的简单性，我觉得我可以回到bash实现并使它更简单(例如，将二进制值保持为int而不是string)。然而，我会让其他人提供一个更简单的bash答案(尽管我认为我们很难找到比jared更简单的答案！

Answer 3

下面是一个使用GNUsed的潜在解决方案，改编自https://codegolf.stackexchange.com/a/204510/95793:

echo "anystr" | eval echo $(gsed 's/\B/{,.}/g') | tr -s " " "\n"
anystr
anyst.r
anys.tr
anys.t.r
any.str
any.st.r
any.s.tr
any.s.t.r
an.ystr
an.yst.r
an.ys.tr
an.ys.t.r
an.y.str
an.y.st.r
an.y.s.tr
an.y.s.t.r
a.nystr
a.nyst.r
a.nys.tr
a.nys.t.r
a.ny.str
a.ny.st.r
a.ny.s.tr
a.ny.s.t.r
a.n.ystr
a.n.yst.r
a.n.ys.tr
a.n.ys.t.r
a.n.y.str
a.n.y.st.r
a.n.y.s.tr
a.n.y.s.t.r

\B是这种方法的关键\B是一个“反向”单词边界标记，即“非单词边界”标记，sed命令在每个点插入{，.}，即。

echo "anystr" | gsed 's/\B/{,.}/g'
a{,.}n{,.}y{,.}s{,.}t{,.}r

{,.}然后由shell展开，即：

eval echo "a{,}"
a a

eval echo "a{,}n{,}"
an an an an

eval echo "a{,.}"
a a.

eval echo "a{,.}n{,}"
an an a.n a.n

eval echo "a{,.}n{,.}"
an an. a.n a.n.

因此，将它们放在一起，您可以获得预期的输出，并且可以使用tr将空格替换为换行符：

echo "anystr" | gsed 's/\B/{,.}/g'
a{,.}n{,.}y{,.}s{,.}t{,.}r

eval echo "a{,.}n{,.}y{,.}s{,.}t{,.}r"
anystr anyst.r anys.tr anys.t.r any.str any.st.r any.s.tr any.s.t.r an.ystr an.yst.r an.ys.tr an.ys.t.r an.y.str an.y.st.r an.y.s.tr an.y.s.t.r a.nystr a.nyst.r a.nys.tr a.nys.t.r a.ny.str a.ny.st.r a.ny.s.tr a.ny.s.t.r a.n.ystr a.n.yst.r a.n.ys.tr a.n.ys.t.r a.n.y.str a.n.y.st.r a.n.y.s.tr a.n.y.s.t.r

eval echo "a{,.}n{,.}y{,.}s{,.}t{,.}r" | tr -s " " "\n"
anystr
anyst.r
anys.tr
anys.t.r
any.str
any.st.r
any.s.tr
any.s.t.r
an.ystr
an.yst.r
an.ys.tr
an.ys.t.r
an.y.str
an.y.st.r
an.y.s.tr
an.y.s.t.r
a.nystr
a.nyst.r
a.nys.tr
a.nys.t.r
a.ny.str
a.ny.st.r
a.ny.s.tr
a.ny.s.t.r
a.n.ystr
a.n.yst.r
a.n.ys.tr
a.n.ys.t.r
a.n.y.str
a.n.y.st.r
a.n.y.s.tr
a.n.y.s.t.r

此外，您不需要使用 eval，它仅用于删除“步骤”，例如

echo "anystr" | gsed 's/\B/{,.}/g'
a{,.}n{,.}y{,.}s{,.}t{,.}r

echo a{,.}n{,.}y{,.}s{,.}t{,.}r | tr -s " " "\n"
anystr
anyst.r
anys.tr
anys.t.r
any.str
any.st.r
any.s.tr
any.s.t.r
an.ystr
an.yst.r
an.ys.tr
an.ys.t.r
an.y.str
an.y.st.r
an.y.s.tr
an.y.s.t.r
a.nystr
a.nyst.r
a.nys.tr
a.nys.t.r
a.ny.str
a.ny.st.r
a.ny.s.tr
a.ny.s.t.r
a.n.ystr
a.n.yst.r
a.n.ys.tr
a.n.ys.t.r
a.n.y.str
a.n.y.st.r
a.n.y.s.tr
a.n.y.s.t.r