Autor Tema: Permutación cíclica con repeticiones (?)

0 Usuarios y 1 Visitante están viendo este tema.

18 Abril, 2021, 01:56 pm
Leído 304 veces

huevomilenio

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 5
  • País: es
  • Karma: +0/-0
Hola, necesitaría saber cómo calcular las posibles combinaciones de 4 dígitos cuyos valores pueden ser 0, 1, 2 y 3.

0000, 1111, 2222, 3333, 0001, 0010, 0100, 1000 etc.

Creo que tiene que ver con permutaciones circulares, pero en mi caso, como veis, los elementos pueden repetirse.

Cada combinación de 4 dígitos representa un ciclo de una onda. Por lo que, a efectos prácticos las combinaciones 0001, 0010, 0100 y 1000 son iguales, solo que desplazadas. Necesitaría poder descartar estos elementos que, desplazados, sean iguales entre sí.

Existe alguna variante de permutación cíclica que permita esto, o alguna otra forma de calcularlo?

Muchas gracias de antemano.

18 Abril, 2021, 04:47 pm
Respuesta #1

robinlambada

  • Moderador Global
  • Mensajes: 3,911
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.
Hola, necesitaría saber cómo calcular las posibles combinaciones de 4 dígitos cuyos valores pueden ser 0, 1, 2 y 3.

0000, 1111, 2222, 3333, 0001, 0010, 0100, 1000 etc.

Creo que tiene que ver con permutaciones circulares, pero en mi caso, como veis, los elementos pueden repetirse.

Cada combinación de 4 dígitos representa un ciclo de una onda. Por lo que, a efectos prácticos las combinaciones 0001, 0010, 0100 y 1000 son iguales, solo que desplazadas. Necesitaría poder descartar estos elementos que, desplazados, sean iguales entre sí.

Existe alguna variante de permutación cíclica que permita esto, o alguna otra forma de calcularlo?

Muchas gracias de antemano.

Entiendo que el orden no importa, si es así se trata de combinaciones con repetición de 4 elementos tomados de 4 en 4.

\( CR_ {4,4}=\begin{pmatrix}{4+4-1}\\{4}\end{pmatrix} \)

Saludos.
Envejecer es como escalar una gran montaña: mientras se sube las fuerzas disminuyen, pero la mirada es más libre, la vista más amplia y serena.

La verdadera juventud una vez alcanzada, nunca se pierde.

18 Abril, 2021, 06:01 pm
Respuesta #2

huevomilenio

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 5
  • País: es
  • Karma: +0/-0
Entiendo que el orden no importa, si es así se trata de combinaciones con repetición de 4 elementos tomados de 4 en 4.

\( CR_ {4,4}=\begin{pmatrix}{4+4-1}\\{4}\end{pmatrix} \)

Saludos.


Muchísimas gracias por la ayuda. Estaba bastante perdido. Ya tengo mis 35 combinaciones. 😅

18 Abril, 2021, 06:16 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 9,753
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Entiendo que el orden no importa, si es así se trata de combinaciones con repetición de 4 elementos tomados de 4 en 4.

\( CR_ {4,4}=\begin{pmatrix}{4+4-1}\\{4}\end{pmatrix} \)

¿Seguro que el orden no importa? Por la explicación de huevomilenio, yo entiendo que 1200 y 2100 tienen que contarse como casos distintos.

18 Abril, 2021, 06:23 pm
Respuesta #4

huevomilenio

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 5
  • País: es
  • Karma: +0/-0
Entiendo que el orden no importa, si es así se trata de combinaciones con repetición de 4 elementos tomados de 4 en 4.

\( CR_ {4,4}=\begin{pmatrix}{4+4-1}\\{4}\end{pmatrix} \)

¿Seguro que el orden no importa? Por la explicación de huevomilenio, yo entiendo que 1200 y 2100 tienen que contarse como casos distintos.

😱 Tienes razón, me acabo de dar cuenta. De hecho he utilizado una calculadora pero no me había fijado en que sí importa el orden y me faltan muchas combinaciones. ¿Sabes cómo lo puedo calcular, entonces? 🙇🏻‍♂️

18 Abril, 2021, 06:35 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,753
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pidiéndole a mi ordenador que las calcule a lo bruto, si no me he equivocado al programarlo, me salen 70:

{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 2}, {0, 0, 0, 3}, {0, 0, 1, 1}, {0, 0, 1, 2}, {0, 0, 1, 3},
{0, 0, 2, 1}, {0, 0, 2, 2}, {0, 0,  2, 3}, {0, 0, 3, 1}, {0, 0, 3, 2}, {0, 0, 3, 3}, {0, 1, 0, 1},
{0, 1, 0, 2}, {0, 1, 0, 3}, {0, 1, 1, 1}, {0, 1, 1, 2}, {0, 1, 1, 3}, {0, 1, 2, 1}, {0, 1, 2, 2},
{0, 1, 2, 3}, {0, 1, 3, 1}, {0, 1, 3, 2}, {0, 1, 3, 3}, {0, 2, 0, 2}, {0, 2, 0, 3}, {0, 2, 1, 1},
{0, 2, 1, 2}, {0, 2, 1, 3}, {0, 2, 2, 1}, {0, 2, 2, 2}, {0, 2, 2, 3}, {0, 2, 3, 1}, {0, 2, 3, 2},
{0, 2, 3, 3}, {0, 3, 0, 3}, {0, 3, 1, 1}, {0, 3, 1, 2}, {0, 3, 1, 3}, {0, 3, 2, 1}, {0, 3, 2, 2},
{0, 3, 2, 3}, {0, 3, 3, 1}, {0, 3, 3, 2}, {0, 3, 3, 3}, {1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 1, 3},
{1, 1, 2, 2}, {1, 1, 2, 3}, {1, 1, 3, 2}, {1, 1, 3, 3}, {1, 2, 1, 2}, {1, 2, 1, 3}, {1, 2, 2, 2},
{1, 2, 2, 3}, {1, 2, 3, 2}, {1, 2, 3, 3}, {1, 3, 1, 3}, {1, 3, 2, 2}, {1, 3, 2, 3}, {1, 3, 3, 2},
{1, 3, 3, 3}, {2, 2, 2, 2}, {2, 2, 2, 3}, {2, 2, 3, 3}, {2, 3, 2, 3}, {2, 3, 3, 3}, {3, 3, 3, 3}

18 Abril, 2021, 06:45 pm
Respuesta #6

huevomilenio

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 5
  • País: es
  • Karma: +0/-0
Pidiéndole a mi ordenador que las calcule a lo bruto, si no me he equivocado al programarlo, me salen 70:

{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 2}, {0, 0, 0, 3}, {0, 0, 1, 1}, {0, 0, 1, 2}, {0, 0, 1, 3},
{0, 0, 2, 1}, {0, 0, 2, 2}, {0, 0,  2, 3}, {0, 0, 3, 1}, {0, 0, 3, 2}, {0, 0, 3, 3}, {0, 1, 0, 1},
{0, 1, 0, 2}, {0, 1, 0, 3}, {0, 1, 1, 1}, {0, 1, 1, 2}, {0, 1, 1, 3}, {0, 1, 2, 1}, {0, 1, 2, 2},
{0, 1, 2, 3}, {0, 1, 3, 1}, {0, 1, 3, 2}, {0, 1, 3, 3}, {0, 2, 0, 2}, {0, 2, 0, 3}, {0, 2, 1, 1},
{0, 2, 1, 2}, {0, 2, 1, 3}, {0, 2, 2, 1}, {0, 2, 2, 2}, {0, 2, 2, 3}, {0, 2, 3, 1}, {0, 2, 3, 2},
{0, 2, 3, 3}, {0, 3, 0, 3}, {0, 3, 1, 1}, {0, 3, 1, 2}, {0, 3, 1, 3}, {0, 3, 2, 1}, {0, 3, 2, 2},
{0, 3, 2, 3}, {0, 3, 3, 1}, {0, 3, 3, 2}, {0, 3, 3, 3}, {1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 1, 3},
{1, 1, 2, 2}, {1, 1, 2, 3}, {1, 1, 3, 2}, {1, 1, 3, 3}, {1, 2, 1, 2}, {1, 2, 1, 3}, {1, 2, 2, 2},
{1, 2, 2, 3}, {1, 2, 3, 2}, {1, 2, 3, 3}, {1, 3, 1, 3}, {1, 3, 2, 2}, {1, 3, 2, 3}, {1, 3, 3, 2},
{1, 3, 3, 3}, {2, 2, 2, 2}, {2, 2, 2, 3}, {2, 2, 3, 3}, {2, 3, 2, 3}, {2, 3, 3, 3}, {3, 3, 3, 3}

Muchísimas gracias. Precisamente 70 era la respuesta que esperaba obtener, sólo que no entiendo cómo se comprueba. Por si a estas alturas no quedaba claro, no tengo mucha idea de matemáticas, pero ya por tozudez... me gustaría entenderlo. ¿Tiene un nombre concreto este tipo de combinatoria?


18 Abril, 2021, 06:55 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 9,753
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Muchísimas gracias. Precisamente 70 era la respuesta que esperaba obtener, sólo que no entiendo cómo se comprueba. Por si a estas alturas no quedaba claro, no tengo mucha idea de matemáticas, pero ya por tozudez... me gustaría entenderlo. ¿Tiene un nombre concreto este tipo de combinatoria?

No sé. En lo que he hecho yo no hay mucho que entender. Como me ha parecido que lo único que necesitabas era saber cuántas son (y en todo caso, cuáles) en este caso concreto, aunque no tengo tiempo para ponerme a pensar una fórmula (ni sé si será fácil), me ha parecido que te serviría con saber la solución del caso que planteas, así que simplemente le he dicho a mi ordenador que calcule las 256 permutaciones con repetición de 4 elementos y que vaya tachando de la lista todas las que coincidan salvo permutación circular con una anterior.

Vamos, lo mismo que podrías hacer tú escribiéndolas todas en un papel y tachando las repetidas, sólo que el ordenador no se queja si le mandas ese trabajo de chinos. Pura fuerza bruta.   ;D

18 Abril, 2021, 07:26 pm
Respuesta #8

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,580
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 El problema equivale a contar collares de \( 4 \) cuentas y \( 4 \) colores. Un collar de \( n \) cuentas y \( k \) colores es una distribución circular de \( n \) cuentas donde cada una de ellas puede tomar uno de los \( k \) colores disponibles.

 Aquí tienes una introducción al tema:

https://en.wikipedia.org/wiki/Necklace_(combinatorics)

 La fórmula es:

\( N_k(n)=\dfrac{1}{n}\displaystyle\sum_{d\mid n}\varphi(d)k^\dfrac{n}{d} \)

 siendo \( \varphi \) la función de Euler.

 En tu caso estás calculando \( N_4(4) \).

 Hay otras fórmulas equivalentes.

Saludos.

18 Abril, 2021, 07:34 pm
Respuesta #9

robinlambada

  • Moderador Global
  • Mensajes: 3,911
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Entiendo que el orden no importa, si es así se trata de combinaciones con repetición de 4 elementos tomados de 4 en 4.

\( CR_ {4,4}=\begin{pmatrix}{4+4-1}\\{4}\end{pmatrix} \)

¿Seguro que el orden no importa? Por la explicación de huevomilenio, yo entiendo que 1200 y 2100 tienen que contarse como casos distintos.
Solo me fije en el ejemplo, no preste atención a el hecho de que fueran circulares,pues no dio seguridad en el enunciado inicial.

Saludos.
Envejecer es como escalar una gran montaña: mientras se sube las fuerzas disminuyen, pero la mirada es más libre, la vista más amplia y serena.

La verdadera juventud una vez alcanzada, nunca se pierde.