0

I'm attempting to solve an algorithm question.

Given an array, count the number of inversions it has. Do this faster than O(N^2) time.

my first solution which doesn't satisfy O(N^2) uses nested loops:

def getInvCount(arr, n): 

    inv_count = 0
    for i in range(n): 
        for j in range(i + 1, n): 
            if (arr[i] > arr[j]): 
                inv_count += 1

    return inv_count

My attempt at converting to a list comprehension

def getInvCount(arr, n):
    inv_count = 0    
    inv_count = [j for i in range (n) for j in range(i + 1, n) if (arr[i] > arr[j])]
    inv_count += 1
    return inv_count

I'm basing my solution on this link

I understand I'm not getting my syntax correctly, especially inv_count += 1 I have looked for examples where the nested loop needs to return a count and is written using list comprehension but I couldn't find any.

Ideally, the function should tell the number of inversions in an array like so;

def getInvCount(arr, n): 

    inv_count = 0
    for i in range(n): 
        for j in range(i + 1, n): 
            if (arr[i] > arr[j]): 
                inv_count += 1

    return inv_count

#testdata

arr = [1, 20, 6, 4, 5] 
n = len(arr) 
print("Number of inversions are", getInvCount(arr, n))

Output

Number of inversions are 5

with my current solution

def getInvCount(arr, n):
    inv_count = 0    
    inv_count = [j for i in range (n) for j in range(i + 1, n) if (arr[i] > arr[j])]
    inv_count += 1
    return inv_count

#testdata

arr = [1, 20, 6, 4, 5] 
n = len(arr) 
print("Number of inversions are", getInvCount(arr, n))

Output

Traceback (most recent call last):
  File "and.py", line 24, in <module>
    getInvCount(arr, n)) 
  File "and.py", line 16, in getInvCount
    inv_count += 1
TypeError: 'int' object is not iterable
Kenechukwu
  • 105
  • 1
  • 1
  • 12
  • 3
    Converting nested `for` loops to a comprehension with multiple `for`s won't improve this in terms of Big-O. – Mark Jun 05 '19 at 22:56
  • 1
    Did you see [this](https://stackoverflow.com/questions/337664/counting-inversions-in-an-array)? – foxpal Jun 05 '19 at 23:34
  • return sum([1 if (arr[i] > arr[j]) else 0 for i in range(n) for j in range(i+1,n)]) should work but won't be more efficient in terms of complexity – Aurgho Bhattacharjee Jun 06 '19 at 01:56
  • thanks a lot @foxpal this helps me understand complexity very well. – Kenechukwu Jun 10 '19 at 15:52
  • @MarkMeyer I didn't understand complexity very well, but Reddit has put me through ELI5 style, you are correct, it doesn't help since the goal is to reduce the for loops not add them to one line. – Kenechukwu Jun 10 '19 at 15:54
  • @AurghoBhattacharjee thank you! the list comprehension works! if you put that as an answer I will accept, as for the complexity bit, I'm understanding more of it daily and foxpal has linked a resource that explains it very well. – Kenechukwu Jun 10 '19 at 15:56

1 Answers1

1
sum([1 if (arr[i] > arr[j]) else 0 for i in range(n) for j in range(i+1,n)])

should work as a list comprehension answer. I had referred this stackoverflow post a few months ago to do be able to do this.

In terms of time complexity, however, it won't be better than O(N^2).

Aurgho Bhattacharjee
  • 426
  • 2
  • 16