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

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

以下是一个使用GNU sed的潜在解决方案，改编自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是这种方法的关键。CCD_ 3是"逆"字边界标记；非文字基础"；标记，sed命令在这些点中的每个点插入{,.}，即

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

{,.}然后被外壳膨胀，即

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

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而不是字符串(。然而，我会让其他人提供一个更简单的bash答案(尽管我认为我们很难找到比jared更简单的答案！

Answer 3

使用POSIX sh:

dot() {
dot_helper()
case $2 in
'') printf '%sn' "$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