☰

如何打印集合的所有子集？

tag-icon • tag-icon bash shell-script math
如何打印集合的所有子集？

如何使用 bash 脚本打印集合的所有子集。像： {} ， {1} ，‌{2} ，{1,2} for A={1,2} 这是我已经写过的，但我总是认为必须有更好的方法，我的脚本也只打印子集有 1 或 2 名成员，但并非全部

如果您帮助我完成/重写这个脚本，我将不胜感激。

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

答案1

使用binary数组作为每个子集的指示函数：

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

答案2

这是您的程序的工作版本：

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

相关内容