2

次の問題が発生しました。

のようなN個の番号の2つのファイルが与えられた

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は、実際には最初のもののシャッフルバージョンにすぎません。最初のファイルの2つの連続する番号の順序が、2番目のファイル（同じ番号を含む）で何回変更されたかを知りたいです。たとえば、ファイル1では1と2を探し始め、2番目のファイルでは2が1の前に来るため、順序が変更されました。最初のファイルには9、次に0があり、2番目のファイルにも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

2つのファイルが特定のルールに従っていることを願っています。

  • 同量の個別の番号、
  • 両方のファイルに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

スクリーンキャストをテストします。書いたばかりのレコーディングスクリプトをテストするためだけに;）

ここに画像の説明を入力してください

于 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 に答える