Dadas K permutaciones de números de 1 a N en una array 2D arr[][] . La tarea es encontrar la subsecuencia común más larga de estas K permutaciones.
Ejemplos:
Entrada: N = 4, K = 3
arr[][] = {{1, 4, 2, 3},
{4, 1, 2, 3},
{1, 2, 4, 3}}
Salida: 3
Explicación : La subsecuencia común más larga es {1, 2, 3} que tiene una longitud de 3.Entrada: N = 6, K = 3,
arr[][] = {{2, 5, 1, 4, 6, 3},
{5, 1, 4, 3, 2, 6},
{5, 4, 2, 6, 3, 1}}
Salida: 3
Explicación: La subsecuencia común más larga es {5, 4, 6} que tiene una longitud de 3.
Enfoque: Este problema es una extensión de la subsecuencia común más larga . La solución se basa en el concepto de programación dinámica . Siga los pasos a continuación:
- Cree una array 2D (pos[][]) para almacenar la posición de todos los números del 1 al N en cada secuencia, donde pos[i][j] indica la posición del valor j en la i-ésima secuencia.
- Inicialice una array (dp[]) donde dp[i] almacena la subsecuencia común más larga que termina en la posición i .
- Considere la primera secuencia como referencia y para cada elemento de la primera secuencia verifique las posiciones relativas de ellos en otras secuencias.
- Iterar sobre todos los índices j posibles de manera que j < i y ver si el valor en el índice i de la primera secuencia se puede agregar a la subsecuencia creciente más larga que termina en j .
- Esto se hace comprobando si la posición del número arr[0][j] es menor que la posición del valor arr[0][i] en todas las permutaciones. Luego, el valor en arr[0][i] se puede agregar a la secuencia que termina en la posición j.
- Considere la primera secuencia como referencia y para cada elemento de la primera secuencia verifique las posiciones relativas de ellos en otras secuencias.
- Entonces la recurrencia es dp[i] = max(dp[i], 1 + dp[j]) .
- El valor máximo de la array dp[] es la respuesta.
Vea la siguiente ilustración:
Ilustración:
Tome el siguiente ejemplo:
N = 4, K = 3, arr[][] = {{1, 4, 2, 3},
{4, 1, 2, 3},
{1, 2, 4, 3}}
- Forme la array de posición: pos[][] = {{1, 3, 4, 2},
{2, 3, 4, 1},
{1, 2, 4, 3}}
En la primera secuencia, 1 está en la primera posición , 2 en 3ª posición, 3 en 4ª y 4 en 2ª posición. Y así sucesivamente para las demás secuencias.- Inicializamos la array dp[]: la array dp [] se inicializa e inicialmente dp[] = {0, 0, 0, 0}
- Secuencia de referencia: La primera secuencia i{1, 4, 2, 3} se utiliza como secuencia de referencia, es decir, las posiciones relativas de los elementos en otras secuencias se comprueban de acuerdo con esta.
- Para i = 1: dp[1] = 1 porque cualquier secuencia de longitud 1 es una secuencia creciente. Ahora dp[] = {1, 0, 0, 0}
- Para i = 2: ahora se verificará la posición relativa de 4 y 1 en las 3 secuencias. En la 2ª secuencia y la 3ª secuencia no se mantiene la posición relativa. Entonces dp[2] = dp[1]. Ahora dp[] = {1, 1, 0, 0} .
- Para i = 3: Se comprueban las posiciones relativas de (1, 4, 2).
Cuando j = 1, es decir, se verifica la posición relativa del valor de 1 y 2, se cumple la condición pos[ind][arr[1][1]] < pos[ind][arr[1][3]] para todos los ind en el rango [1, K] . Entonces dp[3] = max(dp[3], dp[1]+1) = max(0, 2) = 2.
Ahora dp[] = {1, 1, 2, 0}- Para i = 4: aquí también cuando j = 3, entonces pos[ind][arr[1][3]] < pos[ind][arr[1][4]] para todos los ind en el rango [1, K] . Entonces, el cuarto elemento de la primera secuencia se puede agregar en la subsecuencia creciente más larga que termina en el tercer índice. dp[4] = dp[3] + 1 = 2 + 1 = 3.
Ahora dp[] = {1, 1, 2, 3}- El valor máximo en dp[] es 3 . Por lo tanto, la longitud máxima de la subsecuencia creciente más larga es 3.
Nota: la indexación basada en 0 se utiliza en la implementación real. Aquí se utiliza la indexación basada en 1 para facilitar la comprensión
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to find the longest common
// sub sequence of k permutations.
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest common
// sub sequence of k permutations.
int findLcs(vector<vector<int>> &arr,
int n, int k)
{
// Variable to keep track of the length
// of the longest common sub sequence
int maxLen = 0;
// position array to keep track
// of position of elements
// in each permutation
int pos[k][n];
// Array to store the length of LCS
int dp[n];
for (int i = 0; i < k; i++)
{
for (int j = 0; j < n; j++)
{
pos[i][arr[i][j] - 1] = j;
}
}
// Loop to calculate the LCS
// of all the permutations
for (int i = 0; i < n; i++)
{
dp[i] = 1;
for (int j = 0; j < i; j++)
{
bool good = true;
for (int p = 0; p < k; p++)
{
if (pos[p][arr[0][j] - 1]
> pos[p][arr[0][i] - 1])
{
good = false;
break;
}
}
if (good)
{
dp[i] = max(dp[i], 1 + dp[j]);
maxLen = max(maxLen, dp[i]);
}
}
}
return maxLen;
}
// Driver code
int main()
{
vector<vector<int>> arr =
{{2, 5, 1, 4, 6, 3},
{5, 1, 4, 3, 2, 6},
{5, 4, 2, 6, 3, 1}};
int N = arr[0].size();
int K = 3;
// Function Call
cout << findLcs(arr, N, K);
return 0;
}
Java
// Java code to find the longest common
// sub sequence of k permutations.
import java.util.*;
class GFG{
// Function to find the longest common
// sub sequence of k permutations.
static int findLcs(int[][]arr,
int n, int k)
{
// Variable to keep track of the length
// of the longest common sub sequence
int maxLen = 0;
// position array to keep track
// of position of elements
// in each permutation
int [][]pos = new int[k][n];
// Array to store the length of LCS
int []dp = new int[n];
for (int i = 0; i < k; i++)
{
for (int j = 0; j < n; j++)
{
pos[i][arr[i][j] - 1] = j;
}
}
// Loop to calculate the LCS
// of all the permutations
for (int i = 0; i < n; i++)
{
dp[i] = 1;
for (int j = 0; j < i; j++)
{
boolean good = true;
for (int p = 0; p < k; p++)
{
if (pos[p][arr[0][j] - 1]
> pos[p][arr[0][i] - 1])
{
good = false;
break;
}
}
if (good)
{
dp[i] = Math.max(dp[i], 1 + dp[j]);
maxLen = Math.max(maxLen, dp[i]);
}
}
}
return maxLen;
}
// Driver code
public static void main(String[] args)
{
int[][] arr =
{{2, 5, 1, 4, 6, 3},
{5, 1, 4, 3, 2, 6},
{5, 4, 2, 6, 3, 1}};
int N = arr[0].length;
int K = 3;
// Function Call
System.out.print(findLcs(arr, N, K));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code for the above approach # Function to find the longest common # sub sequence of k permutations. def findLcs(arr, n, k): # Variable to keep track of the length # of the longest common sub sequence maxLen = 0 # position array to keep track # of position of elements # in each permutation pos = [0] * k for i in range(len(pos)): pos[i] = [0] * n # Array to store the length of LCS dp = [0] * n for i in range(k): for j in range(n): pos[i][arr[i][j] - 1] = j # Loop to calculate the LCS # of all the permutations for i in range(n): dp[i] = 1 for j in range(i): good = True for p in range(k): if (pos[p][arr[0][j] - 1] > pos[p][arr[0][i] - 1]): good = False break if (good): dp[i] = max(dp[i], 1 + dp[j]) maxLen = max(maxLen, dp[i]) return maxLen # Driver code arr = [[2, 5, 1, 4, 6, 3], [5, 1, 4, 3, 2, 6], [5, 4, 2, 6, 3, 1]] N = len(arr[0]) K = 3 # Function Call print(findLcs(arr, N, K)) # This code is contributed by Saurabh Jaiswal
C#
// C# code to find the longest common
// sub sequence of k permutations.
using System;
class GFG {
// Function to find the longest common
// sub sequence of k permutations.
static int findLcs(int[, ] arr, int n, int k)
{
// Variable to keep track of the length
// of the longest common sub sequence
int maxLen = 0;
// position array to keep track
// of position of elements
// in each permutation
int[, ] pos = new int[k, n];
// Array to store the length of LCS
int[] dp = new int[n];
for (int i = 0; i < k; i++) {
for (int j = 0; j < n; j++) {
pos[i, arr[i, j] - 1] = j;
}
}
// Loop to calculate the LCS
// of all the permutations
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
bool good = true;
for (int p = 0; p < k; p++) {
if (pos[p, arr[0, j] - 1]
> pos[p, arr[0, i] - 1]) {
good = false;
break;
}
}
if (good) {
dp[i] = Math.Max(dp[i], 1 + dp[j]);
maxLen = Math.Max(maxLen, dp[i]);
}
}
}
return maxLen;
}
// Driver code
public static void Main(string[] args)
{
int[, ] arr = { { 2, 5, 1, 4, 6, 3 },
{ 5, 1, 4, 3, 2, 6 },
{ 5, 4, 2, 6, 3, 1 } };
int N = arr.GetLength(1);
int K = 3;
// Function Call
Console.WriteLine(findLcs(arr, N, K));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the longest common
// sub sequence of k permutations.
function findLcs(arr, n, k)
{
// Variable to keep track of the length
// of the longest common sub sequence
let maxLen = 0;
// position array to keep track
// of position of elements
// in each permutation
let pos = new Array(k);
for (let i = 0; i < pos.length; i++) {
pos[i] = new Array(n)
}
// Array to store the length of LCS
let dp = new Array(n);
for (let i = 0; i < k; i++) {
for (let j = 0; j < n; j++) {
pos[i][arr[i][j] - 1] = j;
}
}
// Loop to calculate the LCS
// of all the permutations
for (let i = 0; i < n; i++) {
dp[i] = 1;
for (let j = 0; j < i; j++) {
let good = true;
for (let p = 0; p < k; p++) {
if (pos[p][arr[0][j] - 1]
> pos[p][arr[0][i] - 1]) {
good = false;
break;
}
}
if (good) {
dp[i] = Math.max(dp[i], 1 + dp[j]);
maxLen = Math.max(maxLen, dp[i]);
}
}
}
return maxLen;
}
// Driver code
let arr =
[[2, 5, 1, 4, 6, 3],
[5, 1, 4, 3, 2, 6],
[5, 4, 2, 6, 3, 1]];
let N = arr[0].length;
let K = 3;
// Function Call
document.write(findLcs(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(N 2 * K)
Espacio auxiliar: O(N * K)
Publicación traducida automáticamente
Artículo escrito por nikhilkumarmishra120 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA