Bash:查找数组的幂集

Question

我需要一个 Bash 脚本来获取一个包含 n 个元素的数组作为输入并返回该数组的幂集。

所以对于 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当且仅当 i 的二进制表示中的第 j 位被设置时，项目才进入第 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'