shell 生成最多'n'个字母的所有排列

cdmah0mi  于 2023-03-13  发布在  Shell
关注(0)|答案(3)|浏览(147)

我想生成长度不超过n的所有字母排列
例如,对于参数2,我希望获得如下列表

a
aa
..
az
...
z
za
..
zz

我尝试使用for循环来生成n越来越大的括号扩展,方法是重复{a..z}^1并将其附加到一个变量中,但这似乎不起作用。

OUT=""

# loop from 1 to first argument
for ((i=1; i<=$1; i++))
do
    OUT+=$(echo $(printf '{a..z}%.0s' {1..$i}))
done

OUT=$(echo $OUT | sort)

echo $OUT
gk7wooem

gk7wooem1#

链式大括号展开不能很好地缩放。最好使用如下函数:

# Usage: perms n [prefix]
perms() {
  if (($1 < 1)); then
    return
  fi

  for pfix in "$2"{a..z}; do
    printf '%s\n' "$pfix"
    perms $(($1 - 1)) "$pfix"
  done
}
$ perms 2
a
aa
ab
ac
...

但如果你坚持,这就是你应该怎么做:

# Usage: perms n
perms() {
  printf -v brace_exp '{a..z}%*s' $(($1 - 1))
  brace_exp=${brace_exp// /'{,{a..z}}'}
  eval "printf '%s\n' $brace_exp"
}
ijxebb2r

ijxebb2r2#

在这种情况下,eval可能是您最好的选择,只要您严格控制brace_string的内容,并且它允许您构建一个可以执行任何操作的大括号扩展列表,就不会存在安全问题。

#!/bin/bash

make_list() {
  brace_string=""
  for ((i=0 ; i < $1 ; i++)) ; do
    brace_string+="{a..z}"
    eval printf "'%s\n'" "${brace_string}"
  done
}

make_list "$1" | sort

{1..$i}或在没有eval的变量中构建大括号扩展列表的问题在于bash解析器在扩展变量之前评估语法,这意味着{1..$i}被当作字符串处理,因为$i不是单个字符或整数(稍后它会被一个整数 * 替换 *,但是bash不能预见未来)。eval通过允许您将所有解析步骤执行两次来解决这个问题,这意味着$i可以在第一次解析时被替换,然后大括号扩展在第二次解析时有效。"$brace_string"在第一次解析时不会被视为大括号扩展,因为变量还没有被time bash替换,执行语法分析,但它可以在第二次解析时通过eval处理。

c6ubokkw

c6ubokkw3#

试试这个Shellcheck-clean pure Bash代码:

#! /bin/bash -p

n=$1
(( n == 0 )) && exit 0
perms=( {z..a} )
while (( (ilast = ${#perms[*]}-1) >= 0 )); do
    p=${perms[ilast]}
    unset 'perms[ilast]'

    printf '%s\n' "$p"
    (( ${#p} < n )) && perms+=( "$p"{z..a} )
done
  • 代码使用数组作为堆栈来实现排列树的迭代depth-first search
  • 它已经在Bash版本3、4和5中进行了测试。

通过以字母大小的组输出最大长度排列,可以使代码显著更快(大约4倍):

#! /bin/bash -p

n=$1
(( n == 0 )) && exit 0
perms=( {z..a} )
while (( (ilast = ${#perms[*]}-1) >= 0 )); do
    p=${perms[ilast]}
    unset 'perms[ilast]'

    printf '%s\n' "$p"
    if (( ${#p} < (n-1) )); then
        perms+=( "$p"{z..a} )
    elif (( ${#p} == (n-1) )); then
        printf '%s\n' "$p"{a..z}
    fi
done
  • 在我的(普通的)测试VM上,这段代码生成了长度为3秒4个、1.5米5个和41米6个的所有排列。

相关问题