How to print all subsets of a set?

Question

How can I print all subsets of a set using bash script. like : {} , {1} ,‌{2} ,{1,2} for A={1,2} this is what I have already write but I always thinks there must be a better way also my script just prints subsets with 1 or two members not all of them

I`ll be thankful if you help me complete/rewrite this script.

#!/bin/bash 

# Created By: Amirreza Firoozi
# License : GPL3+
power() {
   echo $(( $1 ** $2 ))
}
update(){
a=${SET[i]}
b=${SET[j]}
}

read -p "Please Enter the set like A={1,q,9} : " TSET
echo "$TSET" | sed -e 's/.*=//' -e 's/[{}]//g' -e 's/,/\n/g' > TSET.txt
MEM_NUM=$(cat "TSET.txt" | wc -l) 
ZIR_NUM=$(power 2 $MEM_NUM)
mapfile -t SET <TSET.txt
for i in "" ${SET[@]};do
    echo "{$i}"
done
RESIGN(){
i=0
j=1
}
RESIGN
m2(){
     while [ 1 == 1 ];do
    if [ $i == $(($MEM_NUM - 1)) ];then
       break
    fi
    while [ "$j" != $MEM_NUM ];do
       update
         echo "{$a,$b}"
    ((j++))
    done 
 ((i++))
 j=$(($i+1))

done
}
m2
RESIGN

Note that perl has library modules specifically for working with sets (e.g. Set::Scalar has union, difference, intersection, etc functions) or lists (aka arrays, e.g. List::Util and friends). python does too. Many things are much easier in other languages than in sh or bash - the shell's speciality is as a wrapper around running other programs, and isn't particularly good (or convenient) for manipulating data. as @choroba's answer demonstrates, using an associative array (aka a hash) with 0 or 1 values (or null/non-existent vs any value/existent) can be used for sets. — cas, Jul 03 '16 at 05:16

score 2 · Accepted Answer · answered Jul 01 '16 at 10:07

Using a binary array as the indicator function of each subset:

#!/bin/bash

# Prepare the indicator, set to all zeros.    
binary=()
for (( i=0; i<=$#; i++ )) ; do
    binary[i]=0
done

while (( ! binary[$#] )) ; do

    # Print the subset.
    printf '{ '
    for (( j=0; j<$#; j++ )) ; do
        (( i=j+1 ))
        (( binary[j] )) && printf '%s ' ${!i}
    done
    printf '}\n'

    # Increment the indicator.
    for (( i=0; binary[i]==1; i++ )) ; do
        binary[i]=0
    done
    binary[i]=1
done

score 1 · Answer 2 · answered Jul 01 '16 at 10:41

Here's a working version of your program:

#!/bin/bash 

# Created By: Amirreza Firoozi
# License : GPL3+

read -p "Please Enter the set like A={1,q,9} : " TSET
echo "$TSET" | sed -e 's/.*=//' -e 's/[{}]//g' -e 's/,/\n/g' > TSET.txt
MEM_NUM=$(cat "TSET.txt" | wc -l) 
ZIR_NUM=$(( 2 ** MEM_NUM))
mapfile -t SET <TSET.txt

# Created By: Petr Skocik
# License : Public Domain

IFS=,; for((i=0;i<ZIR_NUM;i++)); do
    combo=()
    for((j=0;j<MEM_NUM;j++));do
        (( (i & 2**j) == 0 )) || combo+=( "${SET[j]}" )
    done
    printf '{%s}\n' "${combo[*]}"
done

Beware that this has exponential complexity (nsubsets==2^setsize) and it can't get any better so bash will get very slow for this very soon. — Petr Skocik, Jul 01 '16 at 10:45

How to print all subsets of a set?

2 Answers2