20/11/2019, 08:36:15 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Combinatoria en programación  (Leído 1702 veces)
0 Usuarios y 1 Visitante están viendo este tema.
billy
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 66


Ver Perfil
« : 17/10/2018, 09:14:05 pm »

Hola a todos. Tengo el siguiente problema a resolver, me dan una cadena de longitud [texx]n[/texx], todos los caracteres son diferentes, y me dan un número [texx]k[/texx]. Me piden que muestre todas las combinaciones posibles (sin repetición) de longitud  [texx]k[/texx] que se pueden generar a partir de la cadena dada.

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





Agredecería mucho su ayuda.

 


* 3k.PNG (24.02 KB - descargado 157 veces.)
* 4k.PNG (26.24 KB - descargado 125 veces.)
En línea
Richard R Richard
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 85



Ver Perfil
« Respuesta #1 : 10/11/2019, 10:49:21 pm »

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 [texx]n[/texx] elementos las permutaciones son [texx]c_1=n[/texx].

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

para el tercer elemento tienes [texx] n-2[/texx] elementos adicionales [texx]c_3=n(n-1)(n-2)[/texx]


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

que se puede escribir como  [texx] c_k=\dfrac{n!}{(k-1)!}[/texx]
En línea

Saludos  \(\mathbb {R}^3\)
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 45.421


Ver Perfil
« Respuesta #2 : 12/11/2019, 11:28:16 am »

Hola
 
 Mira por aquí:

https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

Saludos.
En línea
Richard R Richard
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 85



Ver Perfil
« Respuesta #3 : 12/11/2019, 09:39:03 pm »

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

[texx]\displaystyle\binom{n}{k}=\dfrac{n!}{k!(n-k)!}[/texx]

en visual basic puede probar hacer un modulo con
Código:
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:

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.

* formulario_combinatori.png (8.59 KB - descargado 21 veces.)
* combinatoria.zip (5.49 KB - descargado 1 veces.)
En línea

Saludos  \(\mathbb {R}^3\)
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!