Búsqueda de sitios web

Programa Python para contar inversiones de tamaño tres en una matriz determinada


El recuento de inversiones es un método de recuento de pasos mediante el cual podemos calcular el número de pasos de clasificación realizados por una matriz en particular. También es capaz de contar el lapso de tiempo de operación de una matriz. Pero, si queremos ordenar una matriz de manera inversa, el recuento será el número máximo presente en esa matriz.

Array: { 5, 4, 3, 2, 1}  // for the reverse manner
Pairs: {5, 4}, {5,3} , {3,2}, {3,1}, {2,1},{4,3}, {4,2}, {4,1},}, {5,2}, {5,1}
Output: 10
Array: {1, 2, 3, 4, 5}  // for the increasing manner
Pairs: No Pairs
Output: 0
Array: {1,5,2,8,3,4}
Pairs: {5, 2}, {5, 3}, {5, 4}, {8, 3}, {8, 4}
Output: 5

El recuento de inversión indica qué tan lejos está esa matriz en particular de ordenarse en orden creciente. Aquí hay dos procesos particulares para describir esta situación adjuntos con una solución:

  • Para encontrar los elementos más pequeños: Para encontrar el elemento más pequeño de una matriz, necesitamos iterar el índice de n-1 a 0. Al aplicar (a[i]-1), podemos calcular getSum() aquí. El proceso se ejecutará hasta llegar a a[i]-1.

  • Para encontrar el número mayor: Para encontrar el número mayor a partir de un índice, debemos realizar la iteración 0 a n-1. Para cada elemento necesitamos hacer cálculos para cada número hasta a[i]. Réstalo de i. Entonces obtendremos a el número que es mayor que a[i].

Algoritmo para contar inversiones de tamaño tres en una matriz

Aquí en este algoritmo; aprendemos a contar inversiones de tamaño tres en una matriz determinada en un entorno de programación particular.

  • Paso 1 - Empezar

  • Paso 2: declarar una matriz y un recuento de inversiones (como arr[] --> matriz e invCount --> recuento de inversiones)

  • Paso 3 - Bucle interno y=x + 1 a N

  • Paso 4: si el elemento en x es mayor que el elemento en y, índice

  • Paso 5: luego, aumenta el invCount++

  • Paso 6: imprime el par

  • Paso 7 - Terminar

Sintaxis para contar inversiones de tamaño tres en una matriz: -

Se dice que un par (A[i], A[j]) está en inversión si: A[i] > A[j] y i < j

Implementación de C++

int getInversions(int * A, int n) {
   int count = 0;
   for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
         if (A[i] > a[j]) {
            ++count;
         }
      }
   }
   return count;
}

Implementación de Java

public static int getInversions(int[] A, int n) {
   int count = 0;
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (A[i] > A[j]) {
            count += 1;
         }
      }
   }
   return count;
}

Implementación de Python

def getInversions(A, n):
count = 0
for i in range(n):
for j in range(i + 1, n):
if A[i] > A[j]:
   count += 1
return count;

Aquí hemos mencionado las posibles sintaxis para contar inversiones de tamaño tres en una matriz determinada. Y para este método; La complejidad del tiempo es O (N ^2), donde N es el tamaño total de la matriz y; Complejidad espacial: O (1), ya que no se ha utilizado espacio adicional.

Enfoques a seguir

  • Método 1: contar inversiones de tamaño tres en una matriz determinada mediante un programa para contar inversiones de tamaño 3

  • Método 2: mejor método para contar inversiones de tamaño 3

  • Método 3: contar inversiones de tamaño 3 utilizando un árbol indexado binario

Cuente inversiones de tamaño tres en una matriz determinada mediante programa para contar inversiones de tamaño 3

Para un enfoque simple para contar inversiones de tamaño tres, necesitamos ejecutar un bucle para todos los valores posibles de i, j y k. La complejidad del tiempo es O (n ^3) y O (1) refleja el espacio auxiliar.

La condición es -

a[i] > a[j] > a[k] y yo < j < k.

Ejemplo 1

def getInvCount(arr):
   n = len(arr)
   invcount = 0
   for i in range(0,n-1):
      for j in range(i+1 , n):
         if arr[i] > arr[j]:
            for k in range(j+1 , n):
               if arr[j] > arr[k]:
                  invcount += 1
   return invcount
arr = [7 , 16, 2 , 1]
print ("Inversion Count after the operation: %d" %(getInvCount(arr)))

Producción

Inversion Count after the operation: 2

Mejor enfoque para contar inversiones de tamaño 3

En este método consideraremos cada elemento de una matriz como elemento intermedio de inversión. Ayuda a reducir la complejidad. Para este enfoque, la complejidad del tiempo es O (n ^2) y el espacio auxiliar es O (1).

Ejemplo 2

def getInvCount(arr, n):
	invcount = 0

	for i in range(1,n-1):
		small = 0
		for j in range(i+1 ,n):
			if (arr[i] > arr[j]):
				small+=1
		great = 0;
		for j in range(i-1,-1,-1):
			if (arr[i] < arr[j]):
				great+=1
		invcount += great * small
	
	return invcount
arr = [8, 4, 2, 1]
n = len(arr)
print("Inversion Count After The Method Run :",getInvCount(arr, n))

Producción

Inversion Count After The Method Run : 4

Cuente inversiones de tamaño 3 usando un árbol indexado binario

En este método contamos los elementos mayores y también los más pequeños. Luego realice la operación de multiplicación de mayor[] a menor[] y súmela al resultado final. Aquí la complejidad del tiempo es O(n*log(n)) y el espacio auxiliar se denota como O(n).

Ejemplo 3

def getSum( BITree, index):
	sum = 0
	while (index > 0):
		sum += BITree[index]
		index -= index & (-index)

	return sum
def updateBIT(BITree, n, index, val):
	while (index <= n):
		BITree[index] += val
		index += index & (-index)
def getInvCount(arr, n):

	invcount = 0 
	maxElement = max(arr)
	BIT = [0] * (maxElement + 1)
	for i in range(n - 1, -1, -1):

		invcount += getSum(BIT, arr[i] - 1)
		updateBIT(BIT, maxElement, arr[i], 1)
	return invcount
if __name__ =="__main__":
	arr = [8, 4, 2, 1]
	n = 4
	print("Inversion Count After The Operation Done : ",
		getInvCount(arr, n))

Producción

Inversion Count After The Operation Done :  6

Conclusión

De la discusión anterior, hemos aprendido cómo contar inversiones de tamaño tres en una matriz determinada. Espero que con este artículo y los códigos mencionados usando el lenguaje particular, tengas una visión amplia sobre este tema.

Artículos relacionados: