CODEWITHSUNDEEP
arraysalgorithmdynamic-programming
Mighty_L
Mighty_L

Reputation: 93

Find the number of unordered pair in an array

I ran into an interesting algorithm problem:

Given an array of integer, find the number of un-ordered pairs in that array, say given {1, 3, 2}, the answer is 1 because {3, 2} is un-ordered, and for array {3, 2, 1}, the answer is 3 because {3, 2}, {3, 1}, {2, 1}.

Obviously, this can be solved by brute force with O(n^2) running time, or permute all possible pairs then eliminate those invalid pairs.

My question is does any body have any better solution and how would you do it because it seems like a dynamic programming problem. A snippet of code would be helpful

Upvotes: 7

Views: 8394

Answers (5)

CanoodleDaNoodle
CanoodleDaNoodle

Reputation: 11

It was in one of my practice midterms and i think a nested for loop does the job pretty nice.

public static void main(String args[])
{
    int IA[] = {6,2,9,5,8,7};

    int cntr = 0;

    for(int i = 0; i <= IA.length-1;i++)
    {
        for(int j = i; j <= IA.length-1; j++)
        {
            if(IA[i]>IA[j])
            {

                System.out.print("("+IA[i]+","+ IA[j]+")"+";");
                cntr++;
            }

        }
    }

    System.out.println(cntr);

}

Upvotes: 1

Chiranjivee Thakur
Chiranjivee Thakur

Reputation: 140

If you are just looking for the number of un-ordered pair and the array is sorted in ascending order. You can use this formula n * (n - 1) / 2. Suppose your array has n elements, for example 3 in your case. It will be 3 * 2 / 2 = 3. Assuming there are no duplicate elements.

Upvotes: 4

Bunny Rabbit
Bunny Rabbit

Reputation: 8411

You can use a modified version of merge sort to count the number of inversions. The trick is that while merging two sorted sub arrays you can come to know the elements which are out of place. If there are any elements in right subarray which need to go before the ones in left subarray, they are the inverted ones. I've written the code for this in python. You can check the explanation below it for better understanding. If you not able to understand merge sort I'd suggest you to revist merge sort after which this would be intuitive.

def merge_sort(l):
    if len(l) <= 1:
        return (0, l)
    else:
        mid = len(l) / 2
        count_left, ll = merge_sort(l[0:mid])
        count_right, lr = merge_sort(l[mid:])
        count_merge, merged = merge(ll, lr)
        total = count_left + count_right + count_merge
        return total, merged

def merge(left, right):
    li, ri = 0, 0
    merged = []        
    count = 0
    while li < len(left) and ri < len(right):
        if left[li] < right[ri]:
            merged.append(left[li])
            li += 1
        else:
            count += 1
            merged.append(right[ri])
            ri += 1

    if li < len(left):
        merged.extend(left[li:])
    elif ri < len(right):
        merged.extend(right[ri:])
    return count, merged

if __name__ == '__main__':
    # example 
    l = [6, 1 , 2, 3, 4, 5]
    print 'inverse pair count is %s'%merge_sort(l)[0]
  • Merge sort runs in n * log(n) time.
  • for the passed list l, merge_sort returns a tuple (in the form of (inversion_count, list)) of number of inversions and the sorted list
  • Merge step counts the number of inversions and stores it in the variable count.

Upvotes: 3

turingcomplete
turingcomplete

Reputation: 2188

You can use a modified merge-sort algorithm. Merging would look something like this.

merge(a, b):
    i = 0
    j = 0
    c = new int[a.length+b.length]
    inversions = 0
    for(k = 0 ; k < Math.min(a.length, b.length); k++)
        if(a[i] > b[j]):
            inversions++
            c[k] = b[j]
            j++
        else:
            c[k] = a[i]
            i++
    //dump the rest of the longer array in c
    return inversions

Merging is done in O(n) time. Time complexity of the whole merge sort is O(n log n)

Upvotes: 0

kraskevich
kraskevich

Reputation: 18576

It is possible to solve this problem in O(n log n) time using a balanced binary search tree. Here is a pseudo-code of this algorithm:

tree = an empty balanced binary search tree
answer = 0
for each element in the array:
     answer += number of the elements in the tree greater then this element
     add this element to the tree

Upvotes: 7

Related Questions