Foros de matemática
23/08/2017, 07:12:23 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Enumerar combinaciones sin repetición  (Leído 486 veces)
0 Usuarios y 1 Visitante están viendo este tema.
rokeroteam
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1


Ver Perfil
« : 05/06/2017, 09:57:18 am »

Tengo que obtener todas las combinaciones posibles sin haber repetición que haya entre los números del 0 al 36

La fórmula es [texx]\dfrac{m!}{n!(m-n)!}[/texx]

y son [texx]1.947.792[/texx] de seisenas

Incluso se ha logrado crear un algoritmo que las saca pero dice tardar 190 años... ¿alguien sabe alguna forma de sacarlas?, ¿o algún algoritmo eficiente?

muchas gracias al mod que me edito el post asi queda mucho mejor.
En línea
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.384


Ver Perfil
« Respuesta #1 : 05/06/2017, 03:00:02 pm »

Hola

 Bienvenido al foro.

 Recuerda leer y seguir  las reglas del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente.

 En particular debes de cuidar la ortografía; por esta vez te hemos corregido el mensaje desde la administración.

Tengo que obtener todas las combinaciones posibles sin haber repetición que haya entre los números del 0 al 36

La fórmula es [texx]\dfrac{m!}{n!(m-n)!}[/texx]

y son [texx]1.947.792[/texx] de seisenas

Incluso se ha logrado crear un algoritmo que las saca pero dice tardar 190 años... ¿alguien sabe alguna forma de sacarlas?, ¿o algún algoritmo eficiente?

muchas gracias al mod que me edito el post asi queda mucho mejor.

Sería bueno saber exactamente en que sentido quieres "sacarlas", para que lo necesitas. En principio hacer por ejemplo un archivo de texto con todas las posibilidades es tan fácil como inútil.

Entonces trata de contextualizar mejor tu pregunta.

Como introducción a los enfoques más típicos de esta cuestión puedes mirar por aquí:

https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

Saludos.
En línea
dresuer
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 61


BOOOOOOM


Ver Perfil
« Respuesta #2 : 29/06/2017, 04:02:40 pm »

Sí, hay una forma y en este caso podes usar lo que se llama programación dinámica.

Cita
Un algoritmo dinámico busca la resolución la mediante la combinación de subproblemas del mismo tipo. A diferencia de divide et impera, pediremos que los subproblemas se solapen.
Que los subproblemas se solapen significa que el problema lo dividimos en subproblemas que son reutilizados varias veces, o que estos subproblemas comparten subsubproblemas.
Un ejemplo típico es Fibonacci, donde al resolver fib(50) recursivamente, se termina recomputando muchísimas veces fib(3) por ej.

Se divide en top-down y bottom-up, te recomiendo que busques programación dinámica en sí y aprendas sobre ella.

Primero aprendé a como calcular la factorial de un número sin recalcularlo tantas veces utilizando programación dinámica por supuesto.

Y te dejo esto aca:

Código:
#include <stdio.h>
#include <stdlib.h>

#define MAXN 50
#define MAXK 50

int comb(int n, int k) {
  static int table[MAXN][MAXK] = { 0 };

  if (k == 0 || n == k)
    return 1;

  if (table[n][k] != 0)
    return table[n][k];

  table[n][k] = comb(n - 1, k) + comb(n - 1, k - 1);

  return table[n][k];
}

int comb_(int n, int k) {
  int table[n+1][k+1];
  int i, j;

  for (i = 0; i <= n; i++)
    table[i][0] = 1;

  for (i = 0; i <= n; i++)
    table[i][i] = 1;

  for (i = 0; i <= n; i++)
    for (j = 1; j <= k && j < i; j++)
      table[i][j] = table[i - 1][j - 1] + table[i - 1][j];

  return table[n][k];
}

int main(void) {
  printf("%d", comb_(10, 9));

  return 0;
}

El primero es TOP-DOWN y el segundo BOTTOM-UP, los dos son eficientes porque no calculan varias veces lo mismo.

Si implementamos este código:
Código:
int fib(int n)
{
   if ( n <= 1 )
      return n;
   return fib(n-1) + fib(n-2);
}

Pasaría esto:
Código:
                             
                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

La fib(2) y fib(3) se recalcula varias veces, cuando ponemos un numero más grande la cosa empeora todavía más.

De todos modos no sé ni en qué lenguaje lo estás programando.

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

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