es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

¿Cómo puedo contar secuencias que cumplan con estas restricciones?

31 Jul, 2023 Programación

Estoy intentando contar las permutaciones de una secuencia de símbolos I y O, que representan, por ejemplo, personas entrando (I para “adentro”) y saliendo (O para “afuera”) de una habitación. Para un número dado n de símbolos I, debe haber exactamente la misma cantidad de símbolos O, lo que da una longitud total de 2*n para la secuencia. Además, en cualquier punto de una permutación válida, el número de símbolos O debe ser menor o igual al número de símbolos I (ya que no es posible que alguien salga de la habitación cuando está vacía).

Además, tengo un prefijo inicial de símbolos I y O, que representan personas que previamente entraron o salieron de la habitación. La salida solo debe contar las secuencias que comienzan con ese prefijo.

Por ejemplo, para n=1 y un estado inicial de '', el resultado debería ser 1 ya que la única secuencia válida es IO; para n=3 y un estado inicial de II, las permutaciones posibles son
 

IIIOOO
IIOIOO
IIOOIO

 
para un resultado de 3. (Hay cinco formas en que tres personas pueden entrar y salir de la habitación, pero las otras dos implican que la primera persona salga de inmediato).

Supongo que la forma más simple de resolver esto es usando itertools.permutations. Este es mi código hasta ahora:

n=int(input())  ##la longitud real será 2*n
cadena=input()
I_COUNT=cadena.count("I")
O_COUNT=cadena.count("O")
if cadena[0]!="I":
 sys.exit()
if O_COUNT>I_COUNT:
 sys.exit()
perms = [''.join(p) for p in permutations(cadena)]
print(perms)

El objetivo es obtener la permutación de lo que falta de la cadena y agregarlo a la entrada del usuario, entonces ¿cómo puedo agregar la entrada del usuario a la longitud restante de la cadena y obtener el conteo de la permutación?

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para agregar la entrada del usuario a la secuencia restante, simplemente puedes usar la concatenación de cadenas:

    remaining_seq = 'I'*(n-I_COUNT) + 'O'*(n-O_COUNT)
full_seq = string + remaining_seq

    Esto creará una secuencia completa con el prefijo inicial proporcionado por el usuario y la secuencia restante generada en base a n, I_COUNT y O_COUNT.

    Para contar el número de permutaciones válidas, puedes usar un bucle para iterar a través de todas las permutaciones de la secuencia restante y verificar si cumplen con las condiciones (igual número de símbolos I y O, y ningún punto con más símbolos O que I). Aquí tienes un ejemplo de implementación:

    from itertools import permutations

n = int(input())
string = input()

I_COUNT = string.count('I')
O_COUNT = string.count('O')
if string[0] != 'I':
    sys.exit()
if O_COUNT > I_COUNT:
    sys.exit()

remaining_seq = 'I'*(n-I_COUNT) + 'O'*(n-O_COUNT)
full_seq = string + remaining_seq

count = 0
for perm in permutations(remaining_seq):
    valid = True
    n_I = I_COUNT
    n_O = O_COUNT
    for symbol in perm:
        if symbol == 'I':
            n_I += 1
        else:
            n_O += 1
        if n_O > n_I:
            valid = False
            break
    if valid:
        count += 1

print(count)

    Esto debería darte el contador correcto de permutaciones válidas para la secuencia de entrada proporcionada.

Comments are closed.