Generando combinaciones de elementos n en grupos de k -- performance campo con c campo con combinatorics camp codereview Relacionados El problema

Generating combinations of n elements in groups of k


2
vote

problema

Español

He escrito este programa que escribe todas las combinaciones (sin repetición) de n elementos en grupos de k.

Creo que el código es bueno, pero me gusta saber si tiene algunas soluciones mejores (o más rápidas).

Los elementos para combinar son siempre el número de 0 a N-1, el programa llama una función ( 9988777665544331 ) para cada combinación generada.

por ejemplo: usando n = 6 y k = 4 El programa genera la siguiente salida:

  0 1 2 3  0 1 2 4  0 1 2 5  0 1 3 4  0 1 3 5  0 1 4 5  0 2 3 4  0 2 3 5  0 2 4 5  0 3 4 5  1 2 3 4  1 2 3 5  1 2 4 5  1 3 4 5  2 3 4 5    

El código está a continuación:

  #include <stdio.h>  void newCombo(int *a,int n,int k);  void newCombo(int *a,int n,int k) {     int i;     for(i=0;i<k;i++)         printf("%d ",a[i]);     puts(""); }  int main(int argc,char *argv[]) {     int a[30];     int n,k,p;      do {         printf("Insert n and k - EG: 5 3: ");         if (scanf("%d %d",&n,&k)!=2)             return 1;         if (k>n)             puts("k shall be <= n !");         if (k==0 || n==0)             puts("k and n shall not be 0!");         if (k>30)             puts("k shall be <=30");     } while (k>n || k==0 || n==0 || k>30);      p=0;     a[0]=-1;     do {         if (++a[p]>n-k+p) {             p--;         } else {             if (p<k-1) {                 a[p+1]=a[p];                 p++;             } else {                 newCombo(a,n,k);             }         }     } while(p>=0);      return 0; }   
Original en ingles

I've written this program that writes all the combinations (without repetition) of n elements in groups of k.

I think the code is good, but I like to know if you have some better (or faster) solutions.

The elements to combine are always the number from 0 to n-1, the program calls a function (newCombo()) for each generated combination.

EG: Using n=6 and k=4 the program generates the following output:

0 1 2 3  0 1 2 4  0 1 2 5  0 1 3 4  0 1 3 5  0 1 4 5  0 2 3 4  0 2 3 5  0 2 4 5  0 3 4 5  1 2 3 4  1 2 3 5  1 2 4 5  1 3 4 5  2 3 4 5  

The code is below:

#include <stdio.h>  void newCombo(int *a,int n,int k);  void newCombo(int *a,int n,int k) {     int i;     for(i=0;i<k;i++)         printf("%d ",a[i]);     puts(""); }  int main(int argc,char *argv[]) {     int a[30];     int n,k,p;      do {         printf("Insert n and k - EG: 5 3: ");         if (scanf("%d %d",&n,&k)!=2)             return 1;         if (k>n)             puts("k shall be <= n !");         if (k==0 || n==0)             puts("k and n shall not be 0!");         if (k>30)             puts("k shall be <=30");     } while (k>n || k==0 || n==0 || k>30);      p=0;     a[0]=-1;     do {         if (++a[p]>n-k+p) {             p--;         } else {             if (p<k-1) {                 a[p+1]=a[p];                 p++;             } else {                 newCombo(a,n,k);             }         }     } while(p>=0);      return 0; } 
        

Lista de respuestas

1
 
vote

El bucle principal podría simplificarse un poco

No hay mucho que decir sobre el programa actual. Funciona y parece que está utilizando el método más rápido posible. Básicamente, agrega uno al último elemento de matriz y se mueve a la izquierda cuando ocurre un "desbordamiento". Al final de manejar todos los "desbordamientos", se mueve hacia la derecha, restableciendo cada dígito.

Lo único que cambiaría es básicamente que cuando regrese a la derecha, no hay necesidad de usar el bucle principal para hacerlo. Causa compasas adicionales de (p >= 0) que siempre van a ser verdaderas y extras ++a[p] que son innecesarios. En su lugar, podría manejar moviéndose hacia la derecha en su propio bucle anidado. Aquí es cómo se vería:

  do {     if (++a[p]>n-k+p) {         // Overflow, move to the next element on the left.         p--;         continue;     }     // Resolve overflows by resetting digits to the right.     while (p < k-1) {         a[p+1]=a[p]+1;         p++;     }     newCombo(a,n,k); } while(p>=0);   

Un desafío interesante

Qué pasaría si le pedí que escribiera un programa que imprime la combinación de N'th en lugar de todos ellos. En su ejemplo dado con N = 6 y K = 4, la 0ª combinación sería 0 1 2 33 y la combinación 14 (y la última) sería 9988777665544334 . Encuentro que esta tarea es mucho más difícil (y útil) que generar todas las combinaciones.

 

Main loop could be simplified a little

There's not too much to say about the current program. It works and it seems like it is using the fastest method possible. It basically adds one to the last array element and moves left when an "overflow" happens. At the end of handling all the "overflows", it moves back to the right, resetting each digit.

The one thing that I would change is basically that when you are moving back to the right, there's no need to use the main loop to do that. It causes extra compares of (p >= 0) which are always going to be true and extra ++a[p] which are unnecessary. You could instead handle moving to the right in its own nested loop. Here's how it would look like:

do {     if (++a[p]>n-k+p) {         // Overflow, move to the next element on the left.         p--;         continue;     }     // Resolve overflows by resetting digits to the right.     while (p < k-1) {         a[p+1]=a[p]+1;         p++;     }     newCombo(a,n,k); } while(p>=0); 

An interesting challenge

What if I asked you to write a program that prints out the N'th combination instead of all of them. In your given example with n=6 and k=4, the 0th combination would be 0 1 2 3 and the 14th (and last) combination would be 2 3 4 5. I find this task to be much more difficult (and useful) than generating all combinations.

 
 
       
       

Relacionados problema

10  Función recursiva que genera las permutaciones de una cadena  ( Recursive function that generates the permutations of a string ) 
Estoy buscando una revisión de mi función recursiva que genere las permutaciones de una cadena. ¿Hay mejores formas de hacer esto? var permutations = []; ...

1  Reto de primos consecutivos en Codeeeval.com  ( Consecutive primes challenge at codeeval com ) 
Estoy trabajando a través de un nuevo desafío en Codeeeval.com y creo que estoy obteniendo un resultado correcto, pero no puedo pasar por su alumnador. No est...

3  Encuentra todas las combinaciones distintas de letras en una cadena  ( Find all distinct combinations of letters in a string ) 
Me he estado preparando para las entrevistas y recogiendo moderno C ++. Una pregunta reciente que hice fue encontrar todas las combinaciones (o subconjuntos d...

1  Imprima todos los tamaños posibles de subsecuencias de cadena en C  ( Print out all possible sizes of subsequences of string in c ) 
Por ejemplo, dada una cadena "abcdefghijk", quiero que mi función se imprima: a, b, c, d, e, f, g, h, i, j, k. ab, bc, cd, de, ef, fg, gh, hi, ij, jk ab...

1  Encuentra la frecuencia de combinaciones en un gran conjunto de datos  ( Find frequency of combinations in large data set ) 
Mi preocupación es el rendimiento del Código. Se tarda mucho más de lo que me gustaría. Estaría dispuesto a renunciar a un poco de memoria para un mayor rendi...

7  Generar un diccionario de contraseñas  ( Generate a dictionary of passwords ) 
Tengo un script de Python que genera un diccionario de todas las combinaciones de contraseña posibles de 3 dígitos. Esencialmente funciona solo en la anidació...

4  Permodificar codility  ( Permcheck codility ) 
El siguiente código obtiene un 100% en el Permdeck tarea en la CODILIDAD . Debe ser O (n). La pregunta es: Se da una matriz no vacía que consta de n ent...

3  Mi implementación de permutación lexicográfica en F # es 3x más lenta que C #  ( My implementation of lexicographic permutation in f is 3x slower than c ) 
¿Puede alguien ayudarme con la siguiente micro optimización para el código F # para la permutación lexicográfica? Tengo código en C # que se ejecuta para 0,...

15  Cracker de contraseña de fuerza bruta  ( Brute force password cracker ) 
Escribí este script para una prueba de concepto JavaScript Password Cracker: var charset = " !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_...

1  Encuentra triángulos de la línea  ( Find triangles from line ) 
Tengo algunas líneas que forman triángulos. Me gustaría desafiar la forma más rápida de encontrar todos los triángulos. En particular, el código debe tom...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos