algorithm - 順列符号を検出する簡単なコード

Question

整数の配列があるとします：

1 2 5 3 7 6

これがソートされた方法での数値の偶数順列か奇数順列かを判断する単純なアルゴリズムは何1 2 3 5 6 7ですか? ここでは、パフォーマンスはさほど重要ではありません。シンプルなコーデがいいですね。

Answer 1

簡単なコード (配列 a に n 個の数値が格納されていると仮定):

int f()
{
    int cnt=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if (a[i]>a[j]) cnt++;
    return cnt%2;
}

f() が 0 を返す場合は偶数順列であり、1 を返す場合は奇数です。

Answer 2

O(n log n) の複雑さを持ち、署名を構築するために順列の数をカウントするヒープ ソート アルゴリズムの独自のバージョンを実装してみてください(私が話していることを知っていると思います)。

サンプルコード:

public static void HeapSort(int[] input)
{
    //Build-Max-Heap
    int heapSize = input.Length;
    for (int p = (heapSize - 1) / 2; p >= 0; p--)
        MaxHeapify(input, heapSize, p);

    for (int i = input.Length - 1; i > 0; i--)
    {
        //Swap
        int temp = input[i];
        input[i] = input[0];
        input[0] = temp;

        heapSize--;
        MaxHeapify(input, heapSize, 0);
    }
}

private static void MaxHeapify(int[] input, int heapSize, int index)
{
    int left = (index + 1) * 2 - 1;
    int right = (index + 1) * 2;
    int largest = 0;

    if (left < heapSize && input[left] > input[index])
        largest = left;
    else
        largest = index;

    if (right < heapSize && input[right] > input[largest])
        largest = right;

    if (largest != index)
    {
        int temp = input[index];
        input[index] = input[largest];
        input[largest] = temp;

        MaxHeapify(input, heapSize, largest);
    }
}

Answer 3

ウィキペディアによると、符号は反転 (要素のペアが順不同) の数によって決定されます。それは O(n**2) アルゴリズムを与えます

Answer 4

このベクトルの置換行列の行列式の符号から答えが得られます。