Блог

Главная - Вопросы по программированию - Генерировать все возможные интервалы внутри указанной строки?

Генерировать все возможные интервалы внутри указанной строки?

#python #bash #loops #math #awk

#python #bash #циклы #математика #awk

Вопрос:

У меня есть строки азбуки Морзе с удаленными пробелами, все одинаковой длины.

Скажем, например, ..--.---.. ,

Я хочу сгенерировать все возможные решения в отдельных строках.

Т.е., . . - - . - - - . . , .. - - .- --. . ..- -.- - -. . и т.д.

Какой хороший, эффективный способ сделать это? Я ужасно разбираюсь в такого рода вещах и я в тупике.

Комментарии:

1. Bash почти наверняка неподходящий инструмент для этого. Если строки находятся в файле, заменить их, например, Awk не должно быть сложно; хотя современный язык сценариев, такой как Python, может быть лучшим выбором, если у вас нет предпочтений относительно того, с чего начать.

2. Ожидается, что вопросы о переполнении стека покажут какие-то усилия — если не вашу собственную попытку написания кода, то, по крайней мере, то, что вы искали, что вы нашли, и какие проблемы у вас возникли с применением этих результатов поиска к вашей проблеме.

3. Раньше я спрашивал об этом в интервью. Если это вопрос XY «как я могу найти все возможные английские слова, которые может представлять эта строка?», я бы предложил вместо этого обратиться к английскому словарю в обратном направлении. Таким образом, это не будет O(2^n)

Ответ №1:

Вот один из них в awk. Я просто играл с двоичными преобразованиями awk, когда увидел этот вопрос и решил кое-что попробовать. Он выполняется от i = 0 до 2(длина (азбука Морзе) -1)-1, преобразует i в двоичный код и заменяет все единицы пробелами, а 0 — нулями, например:

 morse=-.-
length(morse)=3 -> 2^(3-1)-1=3
runs 0..3
0==00 -> -0.0- -> -.-
1==01 -> -0.1- -> -. -
2==10 -> -1.0- -> - .-
3==11 -> -1.1- -> - . -

Скрипт:

 $ echo -..- |
  awk '
  function tobin(d,l) {
    r=""
    while(d) {
        r=d%2r
        d=int(d/2)
    }
    return sprintf("%0" l "d",r)
} 
{
    n=split($0,a,"")
    for(i=0;i<=2^(length-1)-1;i  ) {
        split(tobin(i,length-1),b,"")
        for(j=1;j<=n;j  )
            printf "%s%s",a[j],(b[j]?" ":(j==n?ORS:""))
    }
}'

Вывод:

 -..-
-.. -
-. .-
-. . -
- ..-
- .. -
- . .-
- . . -

Ответ №2:

Если вы хотите сделать это в чистом bash, это может оказаться сложным. Идея состоит в том, чтобы использовать расширение фигурных скобок, которое позаботится обо всех возможностях.

 $ a='..--'
$ [[ $a =~ ${a//?/(.)} ]] amp;amp; b=${BASH_REMATCH[*]:1} amp;amp; eval printf "%s\n" ${b// /{," "}})

Как это работает?

Идея, по сути, заключается в преобразовании

 '..--'

в

 .{," "}.{," "}-{," "}-

и пусть bash использует расширение в виде фигурных скобок для создания всех комбинаций.

  1. [[ $a =~ ${a//?/(.)} ]] Тест bash попытается сопоставить регулярное выражение, ${a//?/(.)} которое напоминает (.)(.)(.)(.) . Он сохранит все совпадения в переменной BASH_REMATCH

  2. b=${BASH_REMATCH[*]:1} Элемент BASH_REMATCH с индексом 0 — это часть строки, соответствующая всему регулярному выражению. Элемент BASH_REMATCH с индексом n — это часть строки, соответствующая n-му заключенному в скобки подвыражению. Следовательно, нас интересуют только все части, кроме первой:

     $ [[ $a =~ ${a//?/(.)} ]] amp;amp; echo ${BASH_REMATCH[*]}
..-- . . - -
$ [[ $a =~ ${a//?/(.)} ]] amp;amp; echo ${BASH_REMATCH[*]:1}
. . - -

  3. ${b// /{," "}} Это заменяет все пробелы на {," "} . Это позволит нам использовать расширение в виде фигурных скобок, которое нам нужно будет оценить с помощью eval 

     $ a='..--'
$ [[ $a =~ ${a//?/(.)} ]]
$ b=${BASH_REMATCH[*]:1}
$ echo "${b// /{," "}}"
.{," "}.{," "}-{," "}-