Bash: 求数组的幂集

Question

我需要一个 Bash 脚本来获得一个包含 n 个元素的数组作为输入和 return 该数组的幂集。

所以 array=(a, b, c, d) 的输出应该是

a
ab
abc
abcd
abd
ac
acd
b
bc
bcd
c
cd
d

请注意，任何元素都不应重复（aab、accd、abbc 无效）并且 abc 与 cba 相同（顺序不重要）。

我发现的类似问题的每个解决方案都给出了固定长度（长度 2 或 3 的组合）或允许重复（如 aacd），即使对于其他语言也是如此（并不是说我可以用其他语言做很多事情...... .)

我想到了这个：

string='a b c d'
read -a array <<< "$string"
count="${#array[@]}"
level=0
for (( level = 0; level < $count; level++ )); do
  for (( i = $level; i < $count; i++ )); do
    output+=" ${array[$i]}"
    echo $output
  done
output=''
done

我的输出是

a
a b
a b c
a b c d
b
b c
b c d
c
c d
d

缺少一些条目，例如 ac、ad、abd...

有什么想法吗？

Answer 1

它可以像在任何其他编程语言中一样直接完成，方法是将每个子集解释为二进制数，其中每个位表示是否选择了相应的元素。对于 n 元素集，您从 0 数到 2ⁿ -1 并取 j-th 项进入 i-th 子集当且仅当 j-th 位在i 的二进制表示已设置。

#! /bin/bash

items=(a b c d)
n=${#items[@]}
powersize=$((1 << $n))

i=0
while [ $i -lt $powersize ]
do
    subset=()
    j=0
    while [ $j -lt $n ]
    do
        if [ $(((1 << $j) & $i)) -gt 0 ]
        then
            subset+=("${items[$j]}")
        fi
        j=$(($j + 1))
    done
    echo "'${subset[@]}'"
    i=$(($i + 1))
done

输出：

''
'a'
'b'
'a b'
'c'
'a c'
'b c'
'a b c'
'd'
'a d'
'b d'
'a b d'
'c d'
'a c d'
'b c d'
'a b c d'

Answer 2

假设您的数组是一组 "simple" 个元素，有一个有趣的解决方案涉及 eval 动态生成的大括号表达式。

$ array=(a b c d)
$ printf -v br "{%s,}" "${array[@]}"
$ echo $br
{a,}{b,}{c,}{d,}
$ eval "printf '%s\n' $br"

（它省略了每个 powerset 的一部分的空字符串，但您可以在之后手动添加它。）

Answer 3

这个有效：

$ p(){ eval echo $(printf "{%s,}" "$@"); }
$ p a b c d
abcd abc abd ab acd ac ad a bcd bc bd b cd c d

或者，更便携：

p() {
        [ $# -eq 0 ] && { echo; return; }
        ( shift; p "$@" ) | while read a ; do printf '%b' "$a\n$a\n"; done
}
p "$@"

这样称呼它（如果你想要一行，请使用 echo）：

$ echo $(p a b c d e)
abcde bcde acde cde abde bde ade de abce bce ace ce abe be ae e abcd bcd acd cd abd bd ad d abc bc ac c ab b a<br>

注意：它适用于 "complex" 项的值，只是不要使用 echo。

$ p " a b " "-c d-" "gg hh"
 a b -c d-gg hh
-c d-gg hh
 a b gg hh
gg hh
 a b -c d-
-c d-
 a b

并且，基于每个值的二进制表示的非递归选项（尽管速度较慢）。然而，它主要是 bash，因为它广泛使用算术展开。

#!/bin/bash

powerset(){
[[ $# -eq 0 ]] && { echo "Missing set of arguments" >&2; exit 2; }
local n ns; (( n=$#, ns=1<<n ))

for (( i=1; i<ns ; i++ )); do
    a=''; # printf "%4.4s " "$i"
    for (( j=1; j<=n; j++ )); do
    (( i & 1<<(j-1) )) && a="${a}""${!j}" ;
    done
    echo "$a"
done
}

powerset "$@"

如果需要编号结果，请删除 a='' 后的注释符号 (#)。

Answer 4

在早期答案的基础上使用 eval

eval echo $(sed 's/./{&,}/g' <<< "abcd") | tr ' ' '\n' | sort

会给你

a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d

Bash: 求数组的幂集

Bash: Finding Powerset of array

bash

permutation