K Inverse Pairs Array - Brute Force

Question

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consisting of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo \10ドル^9 + 7\$.

https://leetcode.com/problems/k-inverse-pairs-array/solution/

Brute Force Solution:

from itertools import permutations, combinations
class Solution:
 def kInversePairs(self, n: int, k: int) -> int:
 array = [x for x in range(1,n+1)]
 array_permutations = list(permutations(array))
 memoized = {}
 count = 0
 for each_permutation in array_permutations:
 each_permutation = list(each_permutation)
 if self.has_exactly_k_inverse_pair(k, each_permutation, memoized):
 count += 1
 return count % 1000000007
 def has_exactly_k_inverse_pair(self, k, array, memoized):
 count = 0
 list_of_sequential_pairs = combinations(array, 2)
 for item_i, item_j in list_of_sequential_pairs:
 cached = memoized.get((item_i, item_j), None)
 if not cached:
 result = self.is_inverse_pair((item_i, item_j))
 if result:
 memoized[(item_i, item_j)] = result
 count += 1
 else:
 count += 1
 if count > k:
 return False
 return count == k
 
 def is_inverse_pair(self, tup):
 return tup[0] > tup[1]

I am looking for code review just for the brute force solutions. I am looking to get constructive feedback mainly with:

• Using memoized dictionary for storing True entries only.
• Being able to pass memoized and update it.
• Using tuples as keys in Python.
• Overall best coding practices.

Answer 1

The memoization is not helping. In fact, it's slowing things down considerably. I executed your code for all pairs of n and k from 0 through 9, inclusive: it took 16 seconds on my computer. Then I commented out the memoization infrastructure and the is_inverse_pair() method and instead just tested for item_i > item_j directly: it finished in 6 seconds and got the same result. This failure of memoization was caused by overfactoring: in almost all situations, it hurts both readability and speed to write a function to perform simple mathematical evaluations. I haven't benchmarked it recently, but calling any function (even a no-op) is almost certainly slower than comparing two integers. And when you're doing something that's already fast, there's no benefit to memoization: I would not be surprised if even a dict-lookup is slower than integer comparison (again, I haven't benchmarked it).

The check for count > k is helping. How do I know? Same benchmarking setup: it takes 10 seconds without the guard.

If you care about speed, make it easy to test and measure. My first step when working on your code was to exercise it with a test case across a variety of inputs (as described), put everything in a dict mapping (n, k) inputs to resulting outputs, print that dict and then put it into a big EXPECTED constant in the code. This quickly gave me an automated way to make sure my changes did not mess anything up, and also an easy way to do some simple speed comparisons as I experimented. This programming habit was learned the hard way, through trial, much error, and even more pain. I encourage you to start adopting similar habits, both in your code and in your coding questions on sites like this (give readers some helpful test code to work with, not just your proposed answer).

Don't convert generators to actual sequences needlessly. You don't need array_permutations as an actual list, because you can iterate directly over the values yielded by permutations(array). Doing so speeds things up a bit more: 4.8 seconds for the same benchmark. And the same thing applies to each_permutation: you don't need to listify it. Instead, just pass the generator to the next function, where it will be iterated directly without the cost of creating an actual list. Dropping that change got my simple benchmark down to 4.2 seconds. You also don't need array to be a list. Just give the range directly to permutations() (because n is small in my benchmark, this change had no observable speed-effect for me, but the same principle would apply if n were large).

Tuples make great dict keys. You asked about this, and it's an excellent thing to have in your tool kit. For example, sometimes d[x, y] is a more convenient way to organize data than d[x][y]. Note also that parentheses are not required: you don't need to use d[(x, y)]. The comma creates the tuple, not the parentheses.

Speaking over overfactoring. You can get another small speed boost by dropping has_exactly_k_inverse_pair(). Function calls take time, so if you're really wanting to eek out gains, inline the code. Of course, that can come at a readability cost, but in this case (given the changes noted above), I don't feel too bad about it.

Here's the code I ended up with:

from itertools import permutations, combinations
EXPECTED = {
 (0, 0): 1, (0, 1): 0, (0, 2): 0, (0, 3): 0, (0, 4): 0, (0, 5): 0, (0, 6): 0, (0, 7): 0, (0, 8): 0, (0, 9): 0,
 (1, 0): 1, (1, 1): 0, (1, 2): 0, (1, 3): 0, (1, 4): 0, (1, 5): 0, (1, 6): 0, (1, 7): 0, (1, 8): 0, (1, 9): 0,
 (2, 0): 1, (2, 1): 1, (2, 2): 0, (2, 3): 0, (2, 4): 0, (2, 5): 0, (2, 6): 0, (2, 7): 0, (2, 8): 0, (2, 9): 0,
 (3, 0): 1, (3, 1): 2, (3, 2): 2, (3, 3): 1, (3, 4): 0, (3, 5): 0, (3, 6): 0, (3, 7): 0, (3, 8): 0, (3, 9): 0,
 (4, 0): 1, (4, 1): 3, (4, 2): 5, (4, 3): 6, (4, 4): 5, (4, 5): 3, (4, 6): 1, (4, 7): 0, (4, 8): 0, (4, 9): 0,
 (5, 0): 1, (5, 1): 4, (5, 2): 9, (5, 3): 15, (5, 4): 20, (5, 5): 22, (5, 6): 20, (5, 7): 15, (5, 8): 9, (5, 9): 4,
 (6, 0): 1, (6, 1): 5, (6, 2): 14, (6, 3): 29, (6, 4): 49, (6, 5): 71, (6, 6): 90, (6, 7): 101, (6, 8): 101, (6, 9): 90,
 (7, 0): 1, (7, 1): 6, (7, 2): 20, (7, 3): 49, (7, 4): 98, (7, 5): 169, (7, 6): 259, (7, 7): 359, (7, 8): 455, (7, 9): 531,
 (8, 0): 1, (8, 1): 7, (8, 2): 27, (8, 3): 76, (8, 4): 174, (8, 5): 343, (8, 6): 602, (8, 7): 961, (8, 8): 1415, (8, 9): 1940,
 (9, 0): 1, (9, 1): 8, (9, 2): 35, (9, 3): 111, (9, 4): 285, (9, 5): 628, (9, 6): 1230, (9, 7): 2191, (9, 8): 3606, (9, 9): 5545,
}
def main():
 LIMIT = 10
 got = {
 (n, k) : Solution().kInversePairs(n, k)
 for n in range(LIMIT)
 for k in range(LIMIT)
 }
 assert got == EXPECTED
class Solution:
 def kInversePairs(self, n: int, k: int) -> int:
 count = 0
 for perm in permutations(range(1, n + 1)):
 n = 0
 for item_i, item_j in combinations(perm, 2):
 if item_i > item_j:
 n += 1
 if n > k:
 break
 if n == k:
 count += 1
 return count % 1000000007
if __name__ == '__main__':
 main()