Autor Tema: Combinatoria en programación

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

18 Octubre, 2018, 02:14 am
Leído 2906 veces

billy

  • $$\pi \pi$$
  • Mensajes: 67
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos. Tengo el siguiente problema a resolver, me dan una cadena de longitud \( n \), todos los caracteres son diferentes, y me dan un número \( k \). Me piden que muestre todas las combinaciones posibles (sin repetición) de longitud  \( k \) que se pueden generar a partir de la cadena dada.

Hice 2 casos particulares, para \( k =3,4 \), y \( n=5 \). Pero no sé cómo podría generalizarlo.
Adjunto las imágenes para \( k =3,4 \), respectivamente.





Agredecería mucho su ayuda.

 


11 Noviembre, 2019, 02:49 am
Respuesta #1

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 447
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Aunque un poco tarde la respuesta, quizá le sirva a alguien  interesado a futuro...

Si hay n elementos disponibles de los cuales quieres saber cuántas formas de ordenarlos cuando escoges k elementos de la lista, te piden el numero de permutaciones

que si escoges 1 elemento tienes \( n \) elementos las permutaciones son \( c_1=n \).

si escoges 2 para el segundo elemento tienes \( n-1 \) elementos disponibles , la cantidad de conjuntos diferentes o permutaciones será \( c_2=n(n-1) \)

para el tercer elemento tienes \(  n-2 \) elementos adicionales \( c_3=n(n-1)(n-2) \)


luego para una cantidad genérica \(  k\leqslant n \) tienes \( c_k=n(n-1)(n-2)...(n-(k-1)) \)

que se puede escribir como  \(  c_k=\dfrac{n!}{(k-1)!} \)
Saludos  \(\mathbb {R}^3\)

12 Noviembre, 2019, 03:28 pm
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,105
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino

13 Noviembre, 2019, 01:39 am
Respuesta #3

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 447
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Veo que si tambíen es importante el orden  la cantidad de elementos del conjunto , ya no se trata de permuraciones sino de combinaciones, por lo que la cantidad de elementos   dadon n y k es

\( \displaystyle\binom{n}{k}=\dfrac{n!}{k!(n-k)!} \)

en visual basic puede probar hacer un modulo con
Código: [Seleccionar]
Public a(0 To 52) As Integer
Public n As Integer
Public m As Integer

y un formulario de similar a



con el código

Código: [Seleccionar]

Private Sub Command1_Click()
lista.Clear
If n1.Text = "" Then n1.Text = "2"
If m1.Text = "" Then m1.Text = "1"
L.Visible = True
Lt.Visible = False
Me.Refresh

n = CInt(n1.Text)
m = CInt(m1.Text)
r = 0
Do Until r = m + 1
a(r) = r
r = r + 1
Loop
cnt = 1
cntt = fact(n) / fact(m) / fact(n - m)
Do Until z = 1
    If comprobar(b) Then
        Open archivo.Text For Append As #1  'Crear el archivo plano
        linea = ""
        t = 1
        Do Until t = m + 1
        If a(t) < 27 Then
        caracter = Chr$(a(t) + 64)
        Else
        caracter = Chr$(a(t) + 70)
        End If
        linea = linea & caracter
       
       
        Print #1, caracter,
        t = t + 1
        Loop
        Print #1, "(" & cnt & "/" & cntt & ")"
       
        linea = linea & "  (" & cnt & "/" & cntt & ")"
        Close #1
        cnt = cnt + 1
        lista.AddItem (linea)
        If cnt = cntt + 1 Then
        L.Visible = False
        Lt.Visible = True
        Lt.Refresh
        Me.Refresh
        Exit Sub
        End If
    End If
    x = m
1     a(x) = a(x) + 1
    If a(x) > n Then
    r = x
    Do Until r > m + 1
    a(r) = a(r - 1) + 1
    r = r + 1
    Loop
   
    x = x - 1
    If x <= 0 Then
    L.Visible = False
    Lt.Visible = True
    Lt.Refresh
    Me.Refresh
    Exit Sub
    Else
    GoTo 1
    End If
    End If
Loop
End Sub
Function comprobar(ByVal b As Integer)
comprobar = True
For r = 1 To m - 1
For s = r + 1 To m
If a(r) = a(s) Then
comprobar = False
 End If
Next s
Next r
End Function
Function fact(ByVal b As Integer)
fact = 1
Do Until b < 1
fact = fact * b
b = b - 1
Loop

End Function


Que te genera las posibles combinaciones  con limite en n=52  (que puedes variar por cierto) y te las numera, a la vez te genera un archivo plano si le indicas la ruta a un fichero de salida de texto que puedes poner en un excel.


O puedes usar el que adjunto.
Saludos  \(\mathbb {R}^3\)