insert dots into string recursively/exhaustively

Question

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?

The first idea that comes to mind (from a design perspective) is to think of this problem as counting in binary. The '.' after a character is like a '1' and no dot is like a '0'. Now, you need to count from 0 to 2^(n-1)-1 where n is the length of your string. — Mark, Oct 25 '22 at 23:22

jared_mamrot · Accepted Answer · 2022-10-26T03:56:15.450

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

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

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

simple and works fine. could u explain `eval echo $(gsed 's/\B/{,.}/g') ` a bit plz? — wsdzbm, Oct 25 '22 at 23:57
Wow! So simple - I'm also looking forward to the explanation. A very impressive use of sed for sure (although gsed is new to me and to my MAC). — Mark, Oct 26 '22 at 00:00
Ahh - yep - that makes more sense @ddzzbbwwmm - I'll edit my answer to remove that part. Thanks for the update — jared_mamrot, Oct 26 '22 at 03:55
I wonder if this approach could hit some args length or similar limitation. — LMC, Oct 26 '22 at 14:45
Good question @LMC! I don't think so (e.g. https://unix.stackexchange.com/questions/8326/what-governs-the-limits-of-shell-brace-expansion) but I'm not sure. I suspect you'll be limited by time before an 'args length' limit (or something similar) because the number of words generated increases exponentially based on the number of characters, e.g. `echo a{,.}n{,.}y{,.}` = 8 words (2^3), `echo a{,.}n{,.}y{,.}s{,.}` = 16 words (2^4). You can see how this will quickly require an unreasonable amount of time to complete, e.g. 24 characters takes ~45s and 25 characters takes ~1m 30s on my system. — jared_mamrot, Oct 26 '22 at 22:43

Mark · Answer 2 · 2022-10-26T00:26:16.193

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!

oguz ismail · Answer 3 · 2022-10-27T04:35:09.247

3

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

edited Oct 27 '22 at 04:35

answered Oct 26 '22 at 03:10

oguz ismail

1
16
47
69

insert dots into string recursively/exhaustively

3 Answers3

Explanation

Edit