Bash: Finding Powerset of array

Question

I need a Bash script that will get an array with n elements as input and return the powerset of that array.

So for array=(a, b, c, d) the output should be

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

Note that no element should repeat (aab, accd, abbc are not valid) and that abc is the same as cba (the order is not important).

Every solution to similar problems I found gives either a fixed length (combination of length 2 or 3) or allows repetition (like aacd), even for other languages (not that I can do much with other languages either...)

I came up with this:

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

and my output is

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

It's missing some entries like ac, ad, abd...

Any ideas?

Answer 1

It can be done straight-forwardly just as in any other programming language by interpreting each subset as a binary number where each bit indicates whether the respective element is chosen or not. For an n-element set, you count from 0 to 2ⁿ −1 and take the j-th item into the i-th subset if and only if the j-th bit in the binary representation of i is set.

#! /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

Output:

''
'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

Assuming your array is a set of "simple" elements, there's an interesting solution involving evaling a dynamically generated brace expression.

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

(It omits the empty string which would be the part of every powerset, but you can add that manually afterwards.)