Bash：寻找阵列的Powerset

发布时间：2020-12-16 01:26:03 所属栏目：安全来源：网络整理

导读：我需要一个 Bash脚本,它将获得一个包含n个元素作为输入的数组,并返回该数组的powerset. 所以对于array =(a,b,c,d),输出应该是 aababcabcdabdacacdbbcbcdccdd 请注意,任何元素都不应重复(aab,accd,abbc无效),并且abc与cba相同(顺序并不重要). 我找到的类似问

我需要一个 Bash脚本,它将获得一个包含n个元素作为输入的数组,并返回该数组的powerset.

所以对于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这样的条目……

有任何想法吗？

通过将每个子集解释为二进制数,其可以直接在任何其他编程语言中完成,其中每个位指示是否选择了相应的元素.对于n元素集,从0到2n -1计数,并且当且仅当设置了i的二进制表示中的第j位时,将第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'

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!