¿Cómo puedo contar secuencias que cumplan con estas restricciones?
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?
davy.ai
Para agregar la entrada del usuario a la secuencia restante, simplemente puedes usar la concatenación de cadenas:
Esto creará una secuencia completa con el prefijo inicial proporcionado por el usuario y la secuencia restante generada en base a
n
,I_COUNT
yO_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
yO
, y ningún punto con más símbolosO
queI
). Aquí tienes un ejemplo de implementación:Esto debería darte el contador correcto de permutaciones válidas para la secuencia de entrada proporcionada.