Categoría: combionatrics

Cuente las permutaciones de todos los números enteros hasta N que pueden formar un gráfico acíclico basado en condiciones dadas

Posted on by Rudeus Greyrat

Dado un número entero N, la tarea es encontrar el número de permutaciones de números enteros del rango [1, N] que pueden formar un gráfico acíclico de acuerdo con las siguientes condiciones: Para cada 1 ≤ i ≤ N , encuentre el j más grande tal que 1 ≤ j < i y A[j] > … Continue reading «Cuente las permutaciones de todos los números enteros hasta N que pueden formar un gráfico acíclico basado en condiciones dadas»

Generador de árboles aleatorios utilizando la secuencia de Prüfer con ejemplos

Posted on by Rudeus Greyrat

Dado un número entero N , la tarea es generar un árbol etiquetado al azar de N Nodes con (N – 1) aristas sin formar un ciclo. Nota: La salida generada a continuación es aleatoria y puede no coincidir con la salida generada por el código. Ejemplos:   Entrada: N = 3  Salida:  1 3  1 … Continue reading «Generador de árboles aleatorios utilizando la secuencia de Prüfer con ejemplos»

Minimice los intercambios de caracteres adyacentes para ordenar todos los reordenamientos posibles de la string binaria dada

Posted on by Rudeus Greyrat

Dada una string binaria S de longitud N que consta de 0s , 1s y “?” , donde «?» puede ser reemplazado por 0 o 1 , la tarea es contar la suma de los intercambios mínimos de caracteres adyacentes requeridos para ordenar todos los arreglos posibles de la string en orden no decreciente Dado … Continue reading «Minimice los intercambios de caracteres adyacentes para ordenar todos los reordenamientos posibles de la string binaria dada»

Número de pares cuyo producto es una potencia de 2

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros, la tarea es contar el número total de pares de elementos de la array de la array dada de modo que arr[i] * arr[j] sea la potencia de 2 . Ejemplos: Entrada: arr[] = {2, 4, 7, 2} Salida: 3 Explicación: arr[0] * arr[1] = 8 … Continue reading «Número de pares cuyo producto es una potencia de 2»

Imprime todas las strings posibles de longitud k que se pueden formar a partir de un conjunto de n caracteres

Posted on by Rudeus Greyrat

Dado un conjunto de caracteres y un entero positivo k, imprime todas las strings posibles de longitud k que se pueden formar a partir del conjunto dado. Ejemplos: Input: set[] = {‘a’, ‘b’}, k = 3 Output: aaa aab aba abb baa bab bba bbb Input: set[] = {‘a’, ‘b’, ‘c’, ‘d’}, k = 1 … Continue reading «Imprime todas las strings posibles de longitud k que se pueden formar a partir de un conjunto de n caracteres»

Número de formas de seleccionar exactamente K números pares de una array dada

Posted on by Rudeus Greyrat

Dada una array arr[] de n enteros y un entero K , la tarea es encontrar el número de formas de seleccionar exactamente K números pares de la array dada. Ejemplos:  Entrada: arr[] = {1, 2, 3, 4} k = 1  Salida: 2  Explicación: El número de formas en que podemos seleccionar un número par … Continue reading «Número de formas de seleccionar exactamente K números pares de una array dada»

Recuento de strings binarias de longitud N con al menos X 0 e Y 1

Posted on by Rudeus Greyrat

Dados tres números N, X e Y , encuentre el recuento de strings binarias únicas de longitud N que tengan al menos X 0 e Y 1 . Ejemplos : Entrada: N=5, X=1, Y=2 Salida: 25 Entrada: N=3, X=1, Y=1 Salida: 6 Explicación: Hay 3 strings binarias de longitud 3 con al menos 1 0 … Continue reading «Recuento de strings binarias de longitud N con al menos X 0 e Y 1»

Programa eficiente para imprimir todos los factores primos de un número dado

Posted on by Rudeus Greyrat

Dado un número n , escriba una función eficiente para imprimir todos los factores primos de n . Por ejemplo, si el número de entrada es 12, entonces la salida debería ser «2 2 3». Y si el número de entrada es 315, entonces la salida debería ser «3 3 5 7». Primer enfoque: Los … Continue reading «Programa eficiente para imprimir todos los factores primos de un número dado»

Contar formas de seleccionar N pares de caramelos de distintos colores (Programación Dinámica + Máscara de Bits)

Posted on by Rudeus Greyrat

Dado un número entero N que representa el número de caramelos rojos y azules y una array mat[][] de tamaño N * N , donde mat[i][j] = 1 representa la existencia de un par entre el i – ésimo caramelo rojo y el j -ésimo caramelo azul, la tarea es encontrar el número de formas … Continue reading «Contar formas de seleccionar N pares de caramelos de distintos colores (Programación Dinámica + Máscara de Bits)»

Recuento de números de N dígitos que no han dado prefijos

Posted on by Rudeus Greyrat

Dado un número entero N y un vector de strings prefijos[], la tarea es calcular el total de strings posibles de longitud N desde los caracteres ‘0’ a ‘9’ . tal que los prefijos dados no se pueden usar en ninguna de las strings. Ejemplos:  Entrada: N = 3, prefijos = {“42”} Salida : 990 … Continue reading «Recuento de números de N dígitos que no han dado prefijos»