Given an array arr, we can rearrange it to form another array,let's call it rerranged_arr. The greatness of the array is defined as the number of indices i, 0 <= i < n , where reraranged_arr[i] > arr[i]. That is the element placed after rearragement is greater than the initial value preset at that index

Given the inital array arr, find the maximum possible greatness which can be achieved by some rearrangement of the array

Example arr = [1,3,5,2,1,3,1]

[1,3,5,2,1,3,1] -> original arr

[2,5,1,3,3,1,1] -> optimal rearranged_arr

Here at indices 0,1,3, and 4 in bold, rearraned_arr[i] > arr[i]. it can be shown that this the maximum possible greatness. Thus the answer is 4

my solution is not good , i'm getting memory error

import itertools

def findMaximumGreatness(arr):
    a = list(itertools.permutations(arr, len(arr)))
    dict = {}
    for i in a:
        c = 0
        for j in range(len(i)):
            if i[j] > arr[j]:
                c  = 1
        dict[i] = c
    return max(dict.values())

This is the error:

a = list(itertools.permutations(arr, len(arr)))
MemoryError

I would like some help to optimize the code / different approach

CodePudding user response：

you could try this:

import itertools as it

t = [1,3,5,2,1,3,1]

def rearrage(t):
    perm = it.permutations(t)
    max = 0
    rel = []
    for p in perm:
        tmp = [i for i, j in zip(p,t) if i>j]
        if len(tmp) > max:

            max = len(tmp)
            rel = p
    return max, rel

rearrage(t)

but please pay attention that if you have more than one solutions with let say 4, there will be listed only one and not all of them.

Result:

4  (1, 5, 1, 3, 2, 1, 3)

CodePudding user response：

Here's something that is memory efficient and fast, but it maximizes the differences between array elements and the result is slightly different than your optimal array. Might help nevertheless.

arr = [1, 3, 5, 2, 1, 3, 1]

lookup = sorted(arr)
result_arr = [0] * len(arr)
greatness = 0
for i, m in sorted(enumerate(arr), key=lambda x: x[1]):
    for j, n in enumerate(lookup):
        if n > m and not result_arr[i]:
            result_arr[i] = n
            greatness  = 1
            del lookup[j]
            break
    else:
        result_arr[i] = lookup[-1]
        del lookup[-1]

print(result_arr, greatness)

Output:

[2, 1, 1, 5, 3, 1, 3] 4