<jupyter_start><jupyter_text>Counting Inversions Input: Array A containing some list of integers in some arbitrary order Output: number of inversions = number of pairs (i,j) of array indices with i  A[j] Example: A = [1,3,5,2,4,6]Inversions = (3,2), (5,2), (5,4)Number of inversions = 3Motivation = numerical similarity measure between 2 ranked lists e.g. "colaborative filtering"<jupyter_code>from typing import List, Tuple
def count_inversions(nums: List)-> Tuple[List, int]:
#     print(nums)
    inversions = 0
    if len(nums) == 1:
        return nums, inversions
    half = len(nums) // 2
    L, l_inversions = count_inversions(nums[:half])
    R, r_inversions = count_inversions(nums[half:])
#     print(L, R)
    # merge
    i = j = 0
    res = []
    inversions = l_inversions + r_inversions
    while(i < len(L) and j < len(R)):
        if R[j] < L[i]:
            res.append(R[j])
            j += 1
            inversions += len(L) - i
        else:
            res.append(L[i])
            i += 1
            
    while(i < len(L)):
        res.append(L[i])
        i += 1
    while(j < len(R)):
        res.append(R[j])
        j += 1
    return res, inversions
    
test_list_1 = [1,2,3,4,5,6]
expected_output_1 = [1,2,3,4,5,6]
expected_inversions = 0 
# Test 1
output_list, inversions = count_inversions(test_list_1)
print(output_list)
assert (output_list, inversions) == (expected_output_1, expected_inversions)
# Test 2
test_list = [1,3,5,2,4,6]
expected_output = [1,2,3,4,5,6]
expected_inversions = 3 
#
output_list, inversions = count_inversions(test_list)
print(output_list, inversions)
assert (output_list, inversions) == (expected_output, expected_inversions)
# Test 3
test_list = [6,5,4,3,2,1]
expected_output = [1,2,3,4,5,6]
expected_inversions = 15 
#
output_list, inversions = count_inversions(test_list)
print(output_list, inversions)
assert (output_list, inversions) == (expected_output, expected_inversions)
# Test 4
test_list = [1,2,3,5,4,6,7,9,8]
expected_output = [1,2,3,4,5,6,7,8,9]
expected_inversions = 2
#
output_list, inversions = count_inversions(test_list)
print(output_list, inversions)
assert (output_list, inversions) == (expected_output, expected_inversions)<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 8, 9] 2
{'fraction_non_alphanumeric': 0.13612099644128114, 'fraction_numerical': 0.04403914590747331, 'mean_word_length': 3.878524945770065, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '162507', 'license': 'MIT', 'n_tokens_mistral': 877, 'n_tokens_neox': 841, 'n_words': 195, 'path': 'Counting Inversions.ipynb', 'repo_name': 'davedecoder/coding_challenges', 'size': '2248'}