Перестановка до N букв с использованием BASH

Question

Я хочу генерировать N буквенных перестановок заданной строки с использованием сценариев bash

Я успешно написал код для поиска перестановки заданного слова.Тем не менее, я не могу получить перестановку до N букв.Примечание: я должен избегать использования команд sed и awk.Вот что я попробовал:

#!/bin/bash
x=$1
counter=0
ARRAY=()
function permutate {
    if [ "${#1}" = 1 ]; then
       echo "${2}${1}"
    ARRAY+=("${2}${1}")
    else
        for i in $(seq 0 $((${#1}-1)) ); do
            pre="${2}${1:$i:1}"
            seg1="${1:0:$i}"
            seg2="${1:$((i+1))}"
            seg="${seg1}${seg2}"
            permutate "$seg" "$pre"
        done
    fi
}
permutate $x

Например, если у меня есть слово «JACK» и я хочу перестановки из 3 букв, оно должно дать: JAC KJA JAK и т. Д. Но я не могу показатьсядокопаться до сути.

Answer 1

Чтобы ограничить каждую перестановку 3 символами, мы можем использовать grep.Ограничение до трех символов может вводить дубликаты.Мы используем sort -u для удаления этих дубликатов.

yourPermutationFunction JACK | grep -Eo '^.{3}' | sort -u

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

Кстати: команда crunch может генерировать перестановкислово;вероятно, намного быстрее, чем любая чистая bash-функция:

crunch 0 0 -p JACK | grep -Eo '^.{3}' | uniq

Здесь мы можем использовать uniq вместо sort -u, поскольку crunch всегда генерирует перестановки в отсортированном порядке.
Для подавленияВывод информации crunch добавляет 2>&- непосредственно перед первым |.

Answer 2

Перестановки букв могут быть получены с помощью скобок-расширений. Пример:

$ echo {A,B}{A,B}
AA AB BA BB

Так что идея состоит в том, чтобы немного использовать это расширение. Допустим, у вас есть строка str, тогда вы можете получить расширение скобки как:

$ str="JACK"
$ eval echo "{$(echo "$str" | fold -w1 | paste -sd,)}"
J A C K

Вы можете шаг за шагом увидеть, что это делает:

$ echo "$str" | fold -w1 | paste -sd,
J,A,C,K

• fold -w1 помещает каждый символ $str$ в одну строку
• paste -sd, объединяет все строки в одну строку с запятой между ними.

Нам нужна эта комбинация, поскольку мы не можем использовать sed. Команда eval, в конце концов, активизирует расширение скобки.

Теперь ключ должен повторить расширение скобки n -times. Для этого мы используем printf. Если у вас есть строка "foo", вы можете повторить ее n раз с printf следующим образом:

$ printf "foo%.0s" {1..3}
foofoofoo

Итак, все перестановки с повторениями можно найти как:

$ str="JACK"
$ n=3
$ bracestring=$(printf "{$(echo "$str" | fold -w1 | paste -sd,)}%.0s" $(seq 1 $n))
$ eval echo $bracestring
JJJ JJA JJC JJK JAJ JAA JAC JAK JCJ JCA JCC JCK JKJ JKA JKC JKK AJJ AJA AJC AJK AAJ AAA AAC AAK ACJ ACA ACC ACK AKJ AKA AKC AKK CJJ CJA CJC CJK CAJ CAA CAC CAK CCJ CCA CCC CCK CKJ CKA CKC CKK KJJ KJA KJC KJK KAJ KAA KAC KAK KCJ KCA KCC KCK KKJ KKA KKC KKK

Answer 3

Распечатайте все уникальные перестановки, используя существующий код.

for VAR in "${ARRAY[@]}"; do
    echo ${VAR:0:3}
done

JAC
JAK
JCA
JCK
JKA
JKC
AJC
AJK
ACJ
ACK
AKJ
AKC
CJA
CJK
CAJ
CAK
CKJ
CKA
KJA
KJC
KAJ
KAC
KCJ
KCA

Answer 4

Вот начало использования awk-реализации Алгоритм кучи для генерации перестановок maxLgth подстрок из списка строк:

$ cat npermutations.awk
function get_perm(A,            i, lgth, sep, str) {
    lgth = length(A)
    lgth = (lgth > maxLgth ? maxLgth : lgth)
    for (i=1; i<=lgth; i++) {
        str = str sep A[i]
        sep = " "
    }
    return str
}

function swap(A, x, y,  tmp) {
    tmp  = A[x]
    A[x] = A[y]
    A[y] = tmp
}

function generate(n, A, B,      i) {
    if (n == 1) {
        B[get_perm(A)]
    }
    else {
        for (i=1; i <= n; i++) {
            generate(n - 1, A, B)
            if ((n%2) == 0) {
                swap(A, 1, n)
            }
            else {
                swap(A, i, n)
            }
        }
    }
}

function get_perms(A,B, lgth) {
    lgth = length(A)
    maxLgth = (maxLgth ? maxLgth : lgth)
    generate(lgth, A, B)
}

###################

# Input should be a list of strings
{
    split($0,A)
    delete B
    get_perms(A,B)
    PROCINFO["sorted_in"] = "@ind_str_asc"
    for (perm in B) {
        print perm
    }
}

например, используя sed для преобразования слова в список строк, как ожидает сценарий awk:

$ echo jack | sed 's/./ &/g' | awk -v maxLgth=3 -f npermutations.awk
a c j
a c k
a j c
a j k
a k c
a k j
c a j
c a k
c j a
c j k
c k a
c k j
j a c
j a k
j c a
j c k
j k a
j k c
k a c
k a j
k c a
k c j
k j a
k j c

Преобразование в оболочку, если это действительно то, что вы хотите сделать, но, надеюсь, вы увидите структуру того, как подходить к проблеме. Выше используется GNU awk для sorted_in для сортировки вывода, но вам это не нужно.