insert dots into string recursively/exhaustively-CodePudding

I wanna insert dots into any input string.

For example, input anystr, and output all possibilities

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

It's easy to insert one dot

a=anystr

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

but how to loop over all possibilities for input string of varying length?

CodePudding user response：

Here is one potential solution using GNU sed, adapted from 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

Edit

I'm surprised this command works with BSD sed (per @ddzzbbwwmm's comment below), but I guess it will work with any sed that includes the \B marker.

Explanation

The \B is the key to this approach. \B is an 'inverse' word boundary marker i.e. a "not-a-word-boundary" marker, and the sed command is inserting {,.} at each of these points, i.e.

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

The {,.} is then expanded by the shell, i.e.

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.

So, putting it all together, you get your expected output and you can replace spaces with newlines using 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

Edit 2

Also, you don't need to use eval, that's only used here to remove a 'step', e.g.

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

CodePudding user response：

Here's an implementation using that binary design idea I proposed in the comments:

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

Here are the results:

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

I've recently changed from bash to python as my language of choice. So I was inclined to try this in python as well:

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()

Based on the simplicity of the python implementation, I feel as if I could go back to the bash implementation and make it simpler (for instance, keeping the binary value as a int and not as a string). However, I'll let someone else provide a simpler bash answer (although I think we'll be hard pressed to find an answer simpler than jared's!

CodePudding user response：

Using 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