アレイの単調性を評価するためのアルゴリズム（すなわち、アレイの「sortedness」と判定）

StackOverflow https://stackoverflow.com/questions/2104166

質問

<時間>

編集：うわー、多くの偉大な回答。はい、私は遺伝的アルゴリズムによって実行されるソートの品質を判断するための適応度関数としてこれを使用しています。コストの評価が重要であるように（すなわち、それは、高速好ましくO(n)なければならない。）

<時間> 私がいじる午前AIアプリケーションの一部として、私はその「sortedness」別名、その単調性に基づいて、整数の候補配列を評価することができるようにしたいと思います。現時点では、私が最も長いソートの実行を求めるヒューリスティックを使用して、分裂しています、その配列の長さ：

public double monotonicity(int[] array) {
    if (array.length == 0) return 1d;

    int longestRun = longestSortedRun(array);
    return (double) longestRun / (double) array.length;
}

public int longestSortedRun(int[] array) {

    if (array.length == 0) return 0;

    int longestRun = 1;
    int currentRun = 1;

    for (int i = 1; i < array.length; i++) {
        if (array[i] >= array[i - 1]) {
            currentRun++;
        } else {
            currentRun = 1;
        }

        if (currentRun > longestRun) longestRun = currentRun;
    }

    return longestRun;
}

これは良いスタートですが、それを考慮にソートされたサブシーケンスの「塊」があるかもしれないという可能性を取ることができません。例えば：ます。

{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9}

このアレイは、三ソートサブシーケンスに分割されます。 40％だけがソートされたとして私のアルゴリズムは、それを評価しますが、直感的に、それはより高いスコアを取得する必要があります。この種のもののための標準的なアルゴリズムがありますか？

役に立ちましたか？

解決

私が使用する機能の選択は、あなたがそれを使用するかに非常に強く依存していることを期待しています。あなたの質問に基づいて、私はあなたがソートのプログラムを作成するために、遺伝的システムを使用していることを推測し、これはランキング関数になることです。その場合は、その後、実行速度が非常に重要です。その上で、私はあなたの最長ソート・サブアルゴリズムはかなりよく働くだろう賭けます。それのような音がかなりよく適応度を定義する必要があること。

他のヒント

これは<ストライキ> レーベンシュタインの Damerau-レーベンシュタインの距離 - 配列をソートするために必要なスワップの数。これは、各項目は、それがソートされた配列にする必要がどこからどれだけ離れているかに比例するはずです。

ここでは距離の二乗を合計する単純ルビアルゴリズムです。それはsortednessの良い測定らしい - 。結果が小さくなる2アウトオブオーダー要素がスワップされているたびに、

ap = a.sort
sum = 0
a.each_index{|i| j = ap.index(a[i])-i 
  sum += (j*j)
}
dist = sum/(a.size*a.size)
私はちょうど作っます。

ここでの1

は、隣接する値の各ペアについて、それらの間の数値の差を計算します。第二は、以上最初に等しい場合、そうでない場合sorted合計に追加、unsorted合計にそれを追加します。完了したら、2の比率を取るます。

を計算し、すべてのソートされたサブシーケンスのlenghts、その後、正方形のそれらとそれらを追加します。 あなたが最大に置くどのくらいenphasis校正したい場合は、2よりもパワー異なっを使用します。

私はよく分からない長さのことで、これを正規化するための最良の方法です何を、多分長さ当たり、それを分割乗？

あなたはおそらく探していることはケンドールのタウのです。これは、2つのアレイ間のバブルソートの距離の一対一の機能です。アレイは「ほとんどソート」であるか否かをテストするために、ソートされた配列に対するそのケンダルのタウを計算します。

私はパンケーキ問題と見てお勧めします順列の反転距離。これらのアルゴリズムは、多くの場合、2つの順列（アイデンティティと並べ替え文字列）の間の距離を見つけるために使用されています。この距離尺度は、（単調減少の代わりに、サブ配列を増加させる）ための値でのアカウントより塊に入れ、同様に反転すべきです。 近似値であることもあります多項式時間[PDF] のます。

それは本当にすべてのものを数手段と、この距離関数はかかわらず、あなたのコンテキストで理にかなっている場合に依存します。

それは非常にあなたがのための対策を使用することを意図しているものに依存しますが、これを実行する簡単な方法は、標準ソートアルゴリズムに配列を供給してあることをどのように多くの操作（スワップおよび/または比較）の必要性を測定することです配列をソートするために行わ。

修飾子ラトクリフといくつかの実験とObershelpの

>>> from difflib import SequenceMatcher as sm
>>> a = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> c = [ 0, 1, 9, 2, 8, 3, 6, 4, 7, 5 ]
>>> b = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> b.sort()
>>> s = sm(None, a, b)
>>> s.ratio()
0.69999999999999996
>>> s2 = sm(None, c, b)
>>> s2.ratio()
0.29999999999999999
だから、種類のそれが必要なものを行います。あまりにも必ずのにそれを証明する方法。

どのように総ステップ数対値の増加に伴ってステップ数を数える程度。それはO(n)です。

所属していません StackOverflow
scroll top