寻找最平衡的组合以获得结果

问题描述 投票:0回答:1

我正在编写 bash 脚本,遇到了一个无法解决的问题。

我有 2 个整数数组,

dividers_1
dividers_2
,以及第三个变量
product
,其中包含一个整数。

#!/bin/bash
dividers_1=("1" "2" "4" "6" "8" "9" "12" "16" "18" "24" "32" "36" "48" "64")
dividers_2=("1" "2" "3" "4" "7" "9" "12" "16" "18" "24" "27" "32" "36" "48" "54")
product=16

目的是找到两个数字最平衡的组合,一个来自第一个数组,另一个来自第二个数组(任意顺序),其乘法等于变量

product

最平衡的组合是指乘法的两项尽可能均匀地分布。 例如,如果

product=16
,最平衡的组合将是
4x4
,而
1x16
则分布不均匀。

显然,完美平衡的组合不一定是可能的,因此,如果由于两个表中可用的值而无法实现,那么我们将寻找分布不太均匀的组合。 例如,如果我们考虑前面的表格和

product=64
,虽然
8x8
组合是最平衡的,但这是不可能的,因为其中一个表格的值中不存在8。 所以最平衡的组合就变成了
4x16
(或
16x4
)。

最后,如果无法组合,则返回错误消息。

我感觉解决方案在于递归函数,但我对此不太擅长。 我愿意接受建议。理想的情况是由于脚本最终运行的介质而具有尽可能少的依赖关系。 我目前使用的是 bash 5.2

编辑1: 正如@markp-fuso 所问: 这就是我所说的“均匀分布”的意思。在两项均匀分布的乘法中,理想情况下这两项是相同的,或者至多差异应该是最小的。例如,如果您要查找的产品是 900,则理想分布是 30x30(相差 0)。下一个最平衡的分布是 25x36 或 36x25(相差 11)。依此类推,直到最不平衡的分布,1x900 或 900x1(相差 899) 编辑2: 我已经重写了很多次,也做了很多不同的尝试,以至于我已经陷入了太多的困境。根本没有优化,抱歉。我需要外部帮助来帮助我重新思考。

#!/bin/bash ## find_combo.sh # Both arrays are hard written for convenience. Usually it's generated by another function that find all the dividers from a given number. dividers_1=(1 2 4 6 8 9 12 16 18 24 32 36 48 64) dividers_2=(1 2 3 4 7 9 12 16 18 24 27 32 36 48 54) product=$1 # check if combination is valid is_valid_combination() { local result=$1 for elem in "${dividers_1[@]}" "${dividers_2[@]}"; do if [ "$elem" == "$result" ]; then return 0 # valid fi done return 1 #not valid } # Find the most balanced combination balanced_combination="" min_difference=999999999 #initial value for num1 in "${dividers_1[@]}"; do for num2 in "${dividers_2[@]}"; do result=$((num1 * num2)) difference=$((num1 > num2 ? num1 - num2 : num2 - num1)) if [ "$result" -eq "$product" ] && [ "$difference" -lt "$min_difference" ] && is_valid_combination "$num1" && is_valid_combination "$num2"; then balanced_combination="$num1 x $num2" min_difference="$difference" fi done done # check if a balanced combination is found if [ -n "$balanced_combination" ]; then echo "Found it: $balanced_combination" else echo "Sorry, no combination found for $product" fi

./find_combo.sh 64

应该返回

Found it: 4 x 16
    

bash command-line-interface
1个回答
0
投票

    is_valid_combination()
  • 函数似乎是多余的(即,如果这些变量是从所述数组填充的,为什么要测试
    $num1 / $num2
    是否是数组中的元素?)
    删除 
  • is_valid_combination()
  • 函数,当前代码将按预期工作(例如,
    64 => 4x16
    63 => 7x9
    16 => 4x4
    5 => Sorry, no combo
    
    
  • shell 中的嵌套循环效率不高,尤其是当数组中元素数量增加时。使用相同的算法,使用不同的工具/软件应该可以获得更好的性能(例如,
awk

perl
python
等)。
实现相同逻辑的一种

awk

方法:

$ cat combo
#!/bin/bash

dividers_1=(1 2 4 6 8 9 12 16 18 24 32 36 48 64)
dividers_2=(1 2 3 4 7 9 12 16 18 24 27 32 36 48 54)
product=$1

awk -v prod="${product}" '                                          # assign awk variable "prod" the value of shell variable "product"
BEGIN     { min_diff = 999999999 }
$1 > prod { next }                                                  # both files: if an array element is greater than prod then skip it
FNR==NR   { div1[$1]; next }                                        # 1st file: save value as index in array div1[]
          { num2 = $1                                               # 2nd file: make note of current value as "num2"
            for (num1 in div1) {                                    # loop through inidices of array div1[]
                diff = (num1 > num2 ? num1 - num2 : num2 - num1)    # calculate the difference
                if ( (num1 * num2) == prod && diff < min_diff) {    # if num1 x num2 equals prod and we have a new min diff the ...
                   bal_combo = num1 " x " num2                      # make note of the balanced combo and ...
                   min_diff  = diff                                 # note the new min diff
                }
            }
          }
END       { if (bal_combo)                                          # after both files have been read: if we have a balanced combo (ie, "bal_combo" is not empty) then ...
               print "Found it:", bal_combo
            else
               print "Sorry, no combination found for",prod
          }
' <(printf "%s\n" "${dividers_1[@]}") <(printf "%s\n" "${dividers_2[@]}")

地点:

    <(printf "%s\n" "${dividers_1[@]}")
  • <(printf "%s\n" "${dividers_2[@]}")
    - 使用进程替换将数组提供给
    awk
    ,使它们看起来像文件
    
    
  • 试驾:

$ ./combo 16 Found it: 4 x 4 $ ./combo 64 Found it: 16 x 4 $ ./combo 63 Found it: 9 x 7 $ ./combo 5 Sorry, no combination found for 5

注意事项:

OP 没有提供有关如果多于一组
    num1 / num2
  • a)
    相乘时等于 $product
    b)
    具有相同(最小)差异(例如 64 = 4 x 16
    64 => 16 x 4
    在这种情况下,
  • awk
  • 脚本将记录(并打印)我们处理的第一对
    num1 / num2
    
        
© www.soinside.com 2019 - 2024. All rights reserved.