python - 计算shell脚本中矩阵中沿行和列但不是对角线的连接非零的数量
问题描述
我有一个矩阵。例如 10 x 15 矩阵
$ cat input.txt
2 3 4 5 10 0 2 2 0 1 0 0 0 1 0
0 3 4 6 2 0 2 0 0 0 0 1 2 3 40
0 0 0 2 3 0 3 0 3 1 2 3 1 0 0
1 2 0 4 0 3 4 0 4 1 2 0 0 1 1
0 0 0 0 0 0 10 3 4 12 4 5 12 3 10
26 3 4 5 10 0 2 2 4 1 0 0 0 1 0
0 30 4 6 2 0 2 0 0 0 0 1 2 3 40
0 0 0 2 3 0 0 0 0 1 0 3 1 0 0
1 2 10 4 0 0 4 0 4 1 2 0 0 1 1
0 0 0 0 0 0 0 3 0 0 4 5 0 3 10
我正在寻找所有连接的非零值及其最大值。请看这张图。
所以期望的输出是:
outfile.txt
12 10 (12 is the yellow shaded connected non-zeros with maximum value 10)
42 40 (42 is the light-red shaded connected non-zeros with maximum value 40)
1 1 (The light purple isolated non-zero)
2 2 (The light green connected non-zeros)
15 30 and so on
6 5
1 4
4 10
1 3
很难开发出合适的算法来用 fortran 或 shell 脚本进一步编写它。我正在考虑以下算法,但无法想到接下来会发生什么。
step 1: #Assign the entries with a[ij], i-row, j-column
#Now make different non-zero connected cell arrays (e.g. c1[k],c2[k],c3[k],....etc)
for i in {1..10};do
for j in {1..15};do
if [ a(i,j) != 0 ];then c1[k]=a(i,j); a(i,j)="*" #(assign a(i,j) to c1[k] and
#replace its original value to "*"
#because it should not be considered further)
Step 2: #Now check the left-right-up-down elements of a(i,j), if non-zero
if [ a(i,j-1) !=0 ] && [ a(i,j) !=* ]; then c1[k]=a(i,j-1); a(i,j-1)="*"
if [ a(i,j+1) !=0 ] && [ a(i,j) !=* ]; then c1[k]=a(i,j+1); a(i,j+1)="*"
if [ a(i-1,j) !=0 ] && [ a(i,j) !=* ]; then c1[k]=a(i-1,j); a(i-1,j)="*"
if [ a(i+1,j) !=0 ] && [ a(i,j) !=* ]; then c1[k]=a(i+1,j); a(i+1,j)="*"
Step 3: #continue the same process for each non-zeros until a zero at all-end.
Step 4: #Count the number of elements in c1[k] and find it maximum
解决方案
这是 GNU awk 中的一个:
awk '
function check(x,y,s, v) { # recursively check neighbours
v=m[x][y] # store val
delete m[x][y] # del to avoid loops
if(((x+1) in m) && (y in m[x+1]) && m[x+1][y]) # test if neighbour exists
check(x+1,y,s) # and check it
if((x in m) && ((y+1) in m[x]) && m[x][y+1])
check(x,y+1,s)
if(((x-1) in m) && (y in m[x-1]) && m[x-1][y])
check(x-1,y,s)
if((x in m) && ((y-1) in m[x]) && m[x][y-1])
check(x,y-1,s)
if(v>max[s])
max[s]=v # keep max
set[s]++ # count set size
}
{
for(x=1;x<=NF;x++) # hash values
m[x][NR]=$x
}
END {
for(x in m) # in no particular order
for(y in m[x])
if(m[x][y])
check(x,y,++s) # start checking
for(i in set) # output
print set[i],max[i]
}' file
输出:
12 10
2 2
15 30
42 40
1 4
1 3
6 5
1 1
4 10
推荐阅读
- algorithm - 找到总成本最小的区间子集,它们一起仍然覆盖初始区间
- reactjs - 如何修改 Gatsby Starter Lightbox 以查询特定图片目录?
- parcel - 使用 Pug 和多个入口点设置 Parcel 的问题
- sql - 延长表中列的长度 - 它会在数据库中破坏什么?
- gpu - 在没有 GPU 的情况下运行 RAPIDS 进行开发?
- json - 用 jq 改变子元素
- polymer - 如何通过它的方法重置聚合物铁自动生长文本区域或纸张文本区域?
- elasticsearch - 如何启用嵌套映射?
- json - 在 Swift 中使用不同的 JSON 格式解码日期值?
- javascript - 使用加密模块的 node.js MD5 解密