Array elements all combinations in bash-CodePudding

I need help to find all combinations (sum) of array elements in bash. here is an excerpt from the code:

    #!/bin/bash
array=("31" "-41" "59" "26" "-53" "58" "97" "-93" "-23" "84") # min 1 vlaue
arrLength=("${#array[@]}")
for (( i=0; i < $arrLength; i  ))
do
    #echo "$i"
    for (( j=$i; j > 0; j-- ))
    do
        summ=$(( array[j] ))
        bak=$((array[0]   summ))
        echo "$summ ; $bak"
    done
    echo "_____________________________"
done

This finds the single pairs and the double pairs. What is missing are the three-pairs (e.g. 31 (-41) 59), the combinations of four...and so on. I don't want to hard code it, because the number of elements can change in my program.

For help I would be very grateful. Thank you.

CodePudding user response：

As commented by others, we have 1023 combinations for 10 numbers, excluding the empty set. These combinations can be associated with the bit pattern between 0000000001 and 1111111111. Then would you please try:

#!/bin/bash

array=("31" "-41" "59" "26" "-53" "58" "97" "-93" "-23" "84")
n=${#array[@]}                          # number of elements
for (( i = 1; i < (1 << n); i   )); do  # loop between 1 and 1023
    sum=0; list=()                      # initialize variables
    for (( j = 0; j < n; j   )); do     # loop over the bit slice position
        if (( (1 << j) & i )); then     # if the bit is set
            (( sum  = ${array[j]} ))    # then pick the element to sum
            list =("${array[j]}")       # append to an array to report
        fi
    done
    (IFS=,; printf "(%s) = %d\n"  "${list[*]}" "$sum")
                                        # report the sum of the set
done

First few lines of the output:

(31) = 31
(-41) = -41
(31,-41) = -10
(59) = 59
(31,59) = 90
(-41,59) = 18
(31,-41,59) = 49
<snip>

It will print 1023 lines in total.

CodePudding user response：

One awk idea using a recursive function:

array=("31" "-41" "59" "26" "-53" "58" "97" "-93" "-23" "84")

printf "%s\n" "${array[@]}" |
awk '
function find_sum(i, sum, label,    j) {

      printf "%8s = %s\n",sum,label

      for (j=i 1;j<=FNR;j  )
          find_sum(j, sum item[j], label "   " item[j])
}

    { item[FNR]=$1 }

END { for (i=1;i<=FNR;i  )
          find_sum(i, item[i], item[i])
    }
'

NOTE: since we perform all operations with a single awk call we can reduce the total run time from ~13 seconds (bash looping construct) to ~0.1 second (awk)

This generates:

      31 = 31
     -10 = 31   -41
      49 = 31   -41   59
      75 = 31   -41   59   26
      22 = 31   -41   59   26   -53
      80 = 31   -41   59   26   -53   58
     177 = 31   -41   59   26   -53   58   97
      84 = 31   -41   59   26   -53   58   97   -93
      61 = 31   -41   59   26   -53   58   97   -93   -23
     145 = 31   -41   59   26   -53   58   97   -93   -23   84
     168 = 31   -41   59   26   -53   58   97   -93   84
     154 = 31   -41   59   26   -53   58   97   -23
     238 = 31   -41   59   26   -53   58   97   -23   84
     261 = 31   -41   59   26   -53   58   97   84
     -13 = 31   -41   59   26   -53   58   -93

... snip ...

      35 = 58   -23
     119 = 58   -23   84
     142 = 58   84
      97 = 97
       4 = 97   -93
     -19 = 97   -93   -23
      65 = 97   -93   -23   84
      88 = 97   -93   84
      74 = 97   -23
     158 = 97   -23   84
     181 = 97   84
     -93 = -93
    -116 = -93   -23
     -32 = -93   -23   84
      -9 = -93   84
     -23 = -23
      61 = -23   84
      84 = 84