algorithm - 计算一个文件中两个连续数字的顺序在 BASH 的第二个文件中颠倒了多少次

Question

我遇到了以下问题:

给定 N 个数字的 2 个文件，例如

文件1.dat: 1,2,3,4,5,6,7,8,9,0

file2.dat: 2,5,4,7,6,9,8,1,0,3

file2.dat 实际上只是第一个的改组版本。我想知道第一个文件中两个连续数字的顺序在第二个文件中发生了多少次更改(包含相同的数字)。例如，在第一个文件中，我们开始查找 1 和 2，在第二个文件中，2 在 1 之前出现，因此顺序发生了变化；在第一个文件中有 9，然后是 0，在第二个文件中也保持这个顺序，因为 9 在 0 之前。

我使用的实际数据大致由 26000 个数字组成，它们都是不同的。

我想到了类似的东西:

for(i=0; i<N-1; i++)
    for(j=0; j<N; j++)
      for(k=0 ; k<N; k++)
        if(B[j]==A[i] && B[k]==A[i+1] && k < j )
        count++

     print("The number of inversion is: %d\n",count)

但我不知道如何用 awk 写它(我写了一个小 C 程序，但花了 5 个多小时才给我答案)而且我不知道类似的东西是否能给我一个结果合理的时间。

Answer 1

我希望你的两个文件遵守一定的规则:

• 相同数量的不同数量，
• 两个文件都是单行

我没有做那些格式检查。查看我的解决方案:

awk -F, 'FNR==NR{n=NF;for(i=1;i<=NF;i++)o[i]=$i;next;}
        {for(i=1;i<=NF;i++)v[$i]=i}
        END{ for(i=1;i<=n-1;i++) t+=v[o[i]]>v[o[i+1]]?1:0;
                print "inversions:",t;
        }' file1 file2

测试:

kent$  head file1 file2
==> file1 <==
1,2,3,4,5,6,7,8,9,0

==> file2 <==
2,5,4,7,6,9,8,1,0,3


kent$  awk -F, 'FNR==NR{n=NF;for(i=1;i<=NF;i++)o[i]=$i;next;}
        {for(i=1;i<=NF;i++)v[$i]=i}
        END{ for(i=1;i<=n-1;i++) t+=v[o[i]]>v[o[i+1]]?1:0;
                print "inversions:",t;
        }' file1 file2
inversions: 5

如果你想打印一些调试信息，比如打印反转对，请看这个:

kent$  awk -F, 'FNR==NR{n=NF;for(i=1;i<=NF;i++)o[i]=$i;next;}
        {for(i=1;i<=NF;i++)v[$i]=i}
        END{ for(i=1;i<=n-1;i++) {

        if(v[o[i]]>v[o[i+1]]){
                print "inversion pair foud:"o[i],o[i+1]
                t++;
        }
        }
                print "inversions:",t;
        }' file1 file2

inversion pair foud:1 2
inversion pair foud:3 4
inversion pair foud:4 5
inversion pair foud:6 7
inversion pair foud:8 9
inversions: 5

如果您需要一些其他信息，例如原始索引/顺序，更改顺序，它们也很容易添加。

希望对您有所帮助。

编辑

如果您的数据文件是单列格式。试试这个:

 awk -F, 'FNR==NR{o[NR]=$0;next;}{v[$0]=FNR;n=FNR}
        END{ for(i=1;i<=n-1;i++) t+=v[o[i]]>v[o[i+1]]?1:0;
                print "invertions:",t;
        }' file1 file2

测试截屏。只是为了测试我刚刚写的录音脚本；)