Combinatorial – Página 41

Conteo de strings binarias de longitud N que tienen igual conteo de 0 y 1 y conteo de 1 ≥ conteo de 0 en cada substring de prefijo

julio 5, 2022 Rudeus Greyrat

Dado un entero N , la tarea es encontrar el número de strings binarias posibles de longitud N con una frecuencia igual de 0 y 1 en las que la frecuencia de 1 sea mayor o igual a la frecuencia de 0 en cada substring de prefijo. Ejemplos: Entrada: N = 2 Salida: 1 Explicación: … Continue reading «Conteo de strings binarias de longitud N que tienen igual conteo de 0 y 1 y conteo de 1 ≥ conteo de 0 en cada substring de prefijo»

Número de arrays bitónicas de longitud n y que constan de elementos de 1 a n

julio 5, 2022 Rudeus Greyrat

Para un número dado n (n > 1), necesitamos encontrar el número de formas en que puede hacer una array bitónica de longitud n, que consta de todos los elementos del 1 al n. Nota: [1, 2,…n] y [n, n – 1…2, 1] no se consideran arreglos bitónicos. Ejemplos: Input : n = 3 Output : … Continue reading «Número de arrays bitónicas de longitud n y que constan de elementos de 1 a n»

Teorema de conteo de órbitas o lema de Burnside

julio 5, 2022 Rudeus Greyrat

El lema de Burnside también se conoce a veces como teorema de conteo de órbitas . Es uno de los resultados de la teoría de grupos . Se utiliza para contar objetos distintos con respecto a la simetría. Básicamente nos da la fórmula para contar el número total de combinaciones, donde dos objetos que son … Continue reading «Teorema de conteo de órbitas o lema de Burnside»

String lexicográficamente más grande posible por un costo dado de agregar caracteres

julio 5, 2022 Rudeus Greyrat

Dado un entero W y una array a[] de tamaño 26 donde ai denota el costo de usar el i -ésimo alfabeto, la tarea es encontrar lexicográficamente la string más grande que se puede generar por un costo , W. Ejemplos: Entrada: W = 236, a[] = {1, 1, 2, 33, 4, 6, 9, 7, … Continue reading «String lexicográficamente más grande posible por un costo dado de agregar caracteres»

Número de strings de longitud N sin substring palindrómica

julio 5, 2022 Rudeus Greyrat

Dados dos enteros positivos N, M . La tarea es encontrar el número de strings de longitud N bajo el conjunto alfabético de tamaño M tal que ninguna substring de tamaño mayor que 1 sea palindrómica. Ejemplos: Input : N = 2, M = 3 Output : 6 In this case, set of alphabet are … Continue reading «Número de strings de longitud N sin substring palindrómica»

Número de formas en que un elemento vuelve a su posición inicial en N intercambios en una array de tamaño K

julio 5, 2022 Rudeus Greyrat

Dados dos números K y N , la tarea es encontrar el número de formas en que un elemento en la posición i regresa a su posición inicial en una array de longitud K en N pasos, donde, en cada paso, el elemento puede intercambiarse con cualquier otro elemento en K Ejemplos: Entrada: N = … Continue reading «Número de formas en que un elemento vuelve a su posición inicial en N intercambios en una array de tamaño K»

Combinaciones con repeticiones

julio 5, 2022 Rudeus Greyrat

Supongamos que tenemos una string de longitud-n y queremos generar todas las combinaciones/permutaciones tomadas r a la vez con/sin repeticiones. Hay cuatro conceptos fundamentales en Combinatoria 1) Combinaciones sin repeticiones/sustituciones. 2) Combinaciones con repeticiones/sustituciones. 3) Permutaciones sin repeticiones/sustituciones. 4) Permutaciones con repeticiones/sustituciones. A continuación se muestra una tabla resumen que representa los conceptos fundamentales de la Teoría Combinatoria. … Continue reading «Combinaciones con repeticiones»

Subsecuencia de permutación más larga en una array dada

julio 5, 2022 Rudeus Greyrat

Dada una array arr que contiene N elementos, encuentre la longitud de la subsecuencia más larga tal que sea una permutación válida de una longitud particular. Si no existe tal secuencia de permutación, imprima 0. Ejemplos: Entrada: arr[] = {3, 2, 1, 6, 5} Salida: 3 Explicación: La subsecuencia de permutación más larga será [3, … Continue reading «Subsecuencia de permutación más larga en una array dada»

Número de composiciones de un número natural

julio 5, 2022 Rudeus Greyrat

Dado un número natural n, encuentre el número de formas en que n puede expresarse como una suma de números naturales cuando se toma en consideración el orden. Dos sucesiones que difieren en el orden de sus términos definen composiciones diferentes de su suma. Ejemplos: Input : 4 Output : 8 Explanation All 8 position composition … Continue reading «Número de composiciones de un número natural»

Contar pares de ceros consecutivos

julio 5, 2022 Rudeus Greyrat

Considere una secuencia que comienza con un 1 en una máquina. En cada paso sucesivo, la máquina transforma simultáneamente cada dígito 0 en la secuencia 10 y cada dígito 1 en la secuencia 01. Después del primer paso de tiempo, se obtiene la secuencia 01; después del segundo, la secuencia 1001, después del tercero, la … Continue reading «Contar pares de ceros consecutivos»