bash 中的数组元素所有组合

Question

我需要帮助来查找 bash 中数组元素的所有组合（总和）。这是代码的摘录：

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

这会找到单对和双对。缺少的是三对（例如 31+(-41)+59）、四对的组合……等等。我不想对其进行硬编码，因为元素的数量在我的程序中可能会发生变化。

如有帮助，我将不胜感激。谢谢。

Answer 1

根据其他人的评论，我们有 10 个数字的 1023 种组合，不包括空集。这些组合可以与位模式相关联在 0000000001 和 1111111111 之间。那你试试看:

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

输出的前几行：

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

总共会打印1023行。

Answer 2

一个 awk 使用递归函数的想法：

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]= }

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

注意： 因为我们通过单个 awk 调用执行所有操作，所以我们可以将总运行时间从 ~13 秒（bash 循环结构) ~0.1 秒 (awk)

这会生成：

      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

Answer 3

如果您的记忆可以容纳它，请通过添加新项目复制它来将每个新项目的数组加倍。此解决方案依赖于包含空集（总和 0）来进行初始化。要排除它，请在最后将其删除。

a=(31 -41 59 26 -53 58 97 -93 -23 84)
b=(0)
for i in ${a[@]}; do for j in ${b[@]}; do b+=( $((i+j)) ); done; done

$ echo ${#b[@]}
1024

$ printf '%s\n' ${b[@]}
0
31
-41
-10
59
:
:
86
155
186
114
145

相同的方法包括计算步骤：

a=(31 -41 59 26 -53 58 97 -93 -23 84)
b=("0 = 0")
for i in ${a[@]}; do for j in "${b[@]}"; do b+=("${j%=*}+ $i = $((i+${j#*=}))"); done; done

$ echo ${#b[@]}
1024

$ printf '%s\n' "${b[@]}"
0 = 0
0 + 31 = 31
0 + -41 = -41
0 + 31 + -41 = -10
0 + 59 = 59
:
:
0 + 31 + -41 + 26 + -53 + 58 + 97 + -93 + -23 + 84 = 86
0 + 59 + 26 + -53 + 58 + 97 + -93 + -23 + 84 = 155
0 + 31 + 59 + 26 + -53 + 58 + 97 + -93 + -23 + 84 = 186
0 + -41 + 59 + 26 + -53 + 58 + 97 + -93 + -23 + 84 = 114
0 + 31 + -41 + 59 + 26 + -53 + 58 + 97 + -93 + -23 + 84 = 145

bash 中的数组元素所有组合

Array elements all combinations in bash

linux

arrays

bash

shell

sum