2

我遇到了以下问题：

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

file1.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 个多小时）而且我不知道类似的东西是否可以在合理的时间内给我一个结果.

4

2 回答 2

4

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

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

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

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

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

在此处输入图像描述

于 2013-01-12T18:04:57.923 回答
0

我知道您已经有了一个公认的干净答案。

只是分享：

sgeorge-mn:~ sgeorge$ cat stack.sh 
VALUE1=$1
VALUE2=$2
for POS in `sed 's/,/ /g' file1.dat`
do
((COUNT++))
if [[ $VALUE1 == $POS ]] ; then
    VAL1_POS=$COUNT
fi

if [[ $VALUE2 == $POS ]] ; then
        VAL2_POS=$COUNT
fi
done


for MATCH in `sed 's/,/ /g' file2.dat`
do
((COUNT2++))
if [[ $VALUE1 == $MATCH ]] ; then
        VAL1_POS2=$COUNT2
fi
if [[ $VALUE2 == $MATCH ]] ; then
        VAL2_POS2=$COUNT2
fi
done

if [[ $VAL1_POS -gt $VAL2_POS ]] ; then
    P1=1
fi
if [[ $VAL1_POS2 -gt $VAL2_POS2 ]] ; then
    P2=1
fi

if [[ $VAL1_POS -lt $VAL2_POS ]] ; then
    P1=2
fi
if [[ $VAL1_POS2 -lt $VAL2_POS2 ]] ; then
    P2=2
fi

if [[ $VAL1_POS -eq $VAL2_POS ]] ; then
    P1=3
fi
if [[ $VAL1_POS2 -eq $VAL2_POS2 ]] ; then
    P2=3
fi

if [[ $P1 == $P2 ]]; then
    echo "No order change"
else
    echo "Order changed"
fi

如何执行脚本：

我假设以下：

  • 两个文件具有完全相同的编号，顺序相同。
  • 您不会将不存在的数字（不存在于file*.dat）作为脚本的输入
sgeorge-mn:~ sgeorge$ bash stack.sh 5 7
No order change
sgeorge-mn:~ sgeorge$ bash stack.sh 4 5
Order changed
sgeorge-mn:~ sgeorge$ bash stack.sh 9 0
No order change
sgeorge-mn:~ sgeorge$ bash stack.sh 1 2
Order changed
于 2013-01-12T18:38:24.600 回答