tabla - unidades decenas y centenas

Intentando generar números de 9 dígitos con cada dígito único

Question

Estoy tratando de obtener números de 9 dígitos que tengan dígitos únicos. Mi primer enfoque parece demasiado complejo y sería tedioso escribirlo.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int indx;
    int num;
    int d1, d2, d3, d4, d5, d6, d7, d8, d9;

    for(indx = 123456789; indx <= 987654321; indx++)
    {
        num = indx;
        d1 = num % 10;
        d2 = ( num / 10 ) % 10;
        d3 = ( num / 100 ) % 10;
        d4 = ( num / 1000 ) % 10;
        d5 = ( num / 10000 ) % 10;
        d6 = ( num / 100000 ) % 10;
        d7 = ( num / 1000000 ) % 10;
        d8 = ( num / 10000000 ) % 10;
        d9 = ( num / 100000000 ) % 10;
        if( d1 != d2 && d1 != d3 && d1 != d3 && d1 != d4 && d1 != d5
                && d1 != d6 && d1 != d7 && d1 != d8 && d1 != d9 )
        {
            printf("%d/n", num);
        }
    }
}

Eso es solo comparar el primer número con el resto. Tendría que hacer muchos más para comparar los otros números. ¿Hay una mejor manera de hacer esto?

Answer 1

Aquí hay una solución un poco fea pero muy rápida usando anidado for loops .

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define NINE_FACTORIAL  362880

int main(void) {

  //array where numbers would be saved
  uint32_t* unique_numbers = malloc( NINE_FACTORIAL * sizeof(uint32_t) );
  if( !unique_numbers ) {
    printf("Could not allocate memory for the Unique Numbers array./n");
    exit(1);
  }

  uint32_t n = 0;
  int a,b,c,d,e,f,g,h,i;

  for(a = 1; a < 10; a++) {
    for(b = 1; b < 10; b++) {
    if (b == a) continue;

      for(c = 1; c < 10; c++) {
      if(c==a || c==b) continue;

        for(d = 1; d < 10; d++) {
        if(d==a || d==b || d==c) continue;

          for(e = 1; e < 10; e++) {
          if(e==a || e==b || e==c || e==d) continue;

            for(f = 1; f < 10; f++) {
            if (f==a || f==b || f==c || f==d || f==e) 
                                continue;

              for(g = 1; g < 10; g++) {
              if(g==a || g==b || g==c || g==d || g==e 
                      || g==f) continue;

                for(h = 1; h < 10; h++) {
                if (h==a || h==b || h==c || h==d || 
                 h==e || h==f || h==g) continue;

                  for(i = 1; i < 10; i++) {
                  if (i==a || i==b || i==c || i==d || 
                  i==e || i==f || i==g || i==h) continue;

                  // print the number or
                  // store the number in the array
                  unique_numbers[n++] = a * 100000000
                        + b * 10000000
                        + c * 1000000
                        + d * 100000
                        + e * 10000
                        + f * 1000
                        + g * 100
                        + h * 10
                        + i;

                  }
                }
              }
            }
          }
        }
      }
    }
  }


  // do stuff with unique_numbers array
  // n contains the number of elements

  free(unique_numbers);

  return 0;
}

Lo mismo con algunas macros.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define l_(b,n,c,p,f) { int i; for(i = 1; i < 10; i++) {            /
      int j,r=0; for(j=0;j<p;j++){if(i == c[j]){r=1;break;}}        /
      if(r) continue; c[p] = i; f   } }

#define l_8(b,n,c,p) {                                              /
    int i; for(i=1; i< 10; i++) {int j, r=0;                        /
      for(j=0; j<p; j++) {if(i == c[j]) {r = 1; break;}}            /
      if(r)continue; b[n++] = c[0] * 100000000  + c[1] * 10000000   /
            + c[2] * 1000000 + c[3] * 100000 + c[4] * 10000         /
            + c[5] * 1000 + c[6] * 100 + c[7] * 10 + i; } }

#define l_7(b,n,c,p) l_(b,n,c,p, l_8(b,n,c,8))
#define l_6(b,n,c,p) l_(b,n,c,p, l_7(b,n,c,7))
#define l_5(b,n,c,p) l_(b,n,c,p, l_6(b,n,c,6))
#define l_4(b,n,c,p) l_(b,n,c,p, l_5(b,n,c,5))
#define l_3(b,n,c,p) l_(b,n,c,p, l_4(b,n,c,4))
#define l_2(b,n,c,p) l_(b,n,c,p, l_3(b,n,c,3))
#define l_1(b,n,c,p) l_(b,n,c,p, l_2(b,n,c,2))

#define get_unique_numbers(b,n,c) do {int i; for(i=1; i<10; i++) { /
      c[0] = i; l_1(b,n,c,1) } } while(0)


#define NINE_FACTORIAL  362880

int main(void) {

  //array where numbers would be saved
  uint32_t* unique_numbers = malloc( NINE_FACTORIAL * sizeof(uint32_t) );
  if( !unique_numbers ) {
    printf("Could not allocate memory for the Unique Numbers array./n");
    exit(1);
  }

  int n = 0;
  int current_number[8] = {0};

  get_unique_numbers(unique_numbers, n, current_number);


  // do stuff with unique_numbers array
  // NINE_FACTORIAL is the number of elements


  free(unique_numbers);

  return 0;
}

Estoy seguro de que hay mejores formas de escribir esas macros, pero eso es lo que se me ocurre.

Answer 2

Haga una lista con 10 elementos con valores 0-9. Extraiga elementos aleatorios por rand () / w longitud actual de la lista, hasta que tenga el número de dígitos que desea.

Answer 3

Un poco tarde para la fiesta, pero muy rápido (30 ms aquí) ...

#include <stdio.h>
#define COUNT 9

   /* this buffer is global. intentionally.
   ** It occupies (part of) one cache slot,
   ** and any reference to it is a constant
   */
char ten[COUNT+1] ;

unsigned rec(unsigned pos, unsigned mask);
int main(void)
{
unsigned res;

ten[COUNT] = 0;

res = rec(0, (1u << COUNT)-1);
fprintf(stderr, "Res=%u/n", res);

return 0;
}

/* recursive function: consume the mask of available numbers
** until none is left.
** return value is the number of generated permutations.
*/
unsigned rec(unsigned pos, unsigned mask)
{
unsigned bit, res = 0;

if (!mask) { puts(ten); return 1; }

for (bit=0; bit < COUNT; bit++) {
        if (! (mask & (1u <<bit)) ) continue;
        ten[pos] = ''1'' + bit;
        res += rec(pos+1, mask & ~(1u <<bit));
        }
return res;
}

Answer 4

Una manera simple es crear una matriz con nueve valores distintos, barajarla e imprimir la matriz barajada. Repita tantas veces como sea necesario. Por ejemplo, usando la rand() función estándar como base para barajar ...

#include <stdlib.h>     /*  for srand() and rand */
#include <time.h>       /*  for time() */
#include <stdio.h>      

#define SIZE 10     /*   size of working array.  There are 10 numeric digits, so ....   */
#define LENGTH 9    /*  number of digits we want to output.  Must not exceed SIZE */
#define NUMBER 12   /*  number of LENGTH digit values we want to output */

void shuffle(char *buffer, int size)
{
     int i;
     char temp;
     for (i=size-1; i>0; --i)
     {
          /*  not best way to get a random value of j in [0, size-1] but
               sufficient for illustrative purposes
          */
          int j = rand()%size;
          /* swap buffer[i] and buffer[j] */
          temp = buffer[i];    
          buffer[i] = buffer[j];
          buffer[j] = temp;
     }
}

void printout(char *buffer, int length)
{
      /*  this assumes SIZE <= 10 and length <= SIZE */

      int i;
      for (i = 0; i < length; ++i)
          printf("%d", (int)buffer[i]);
      printf("/n");
}

int main()
{
     char buffer[SIZE];
     int i;
     srand((unsigned)time(NULL));   /*  seed for rand(), once and only once */

     for (i = 0; i < SIZE; ++i)  buffer[i] = (char)i;  /*  initialise buffer */

     for (i = 0; i < NUMBER; ++i)
     {
         /*  keep shuffling until first value in buffer is non-zero */

         do shuffle(buffer, SIZE); while (buffer[0] == 0);
         printout(buffer, LENGTH);
     }
     return 0;
}

Esto imprime una serie de líneas stdout , cada una con 9 dígitos únicos. Tenga en cuenta que esto no evita duplicados.

Answer 5

versión iterativa que usa bits ampliamente

tenga en cuenta que array puede cambiarse a cualquier tipo y establecerse en cualquier orden, esto "contará" los dígitos en un orden determinado

Para obtener más explicaciones, mire mi primera respuesta (que es menos flexible pero mucho más rápida) https://.com/a/31928246/2963099

Para hacerlo iterativo, se necesitaban matrices para mantener el estado en cada nivel

Esto también fue bastante optimizado para lugares que el optimizador no pudo entender

int bit_val(unsigned int v) {
  static const int MultiplyDeBruijnBitPosition2[32] = {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  return MultiplyDeBruijnBitPosition2[(unsigned int)(v * 0x077CB531U) >> 27];
}

void uniq_digits(const int array[], const int length) {
  unsigned int unused[length-1];                    // unused prior
  unsigned int combos[length-1];                    // digits untried
  int digit[length];                                // printable digit
  int mult[length];                                 // faster calcs
  mult[length-1]=1;                                 // start at 1
  for (int i = length-2; i >= 0; --i)
     mult[i]=mult[i+1]*10;                          // store multiplier
  unused[0]=combos[0]=((1<<(length))-1);            // set all bits 0-length
  int depth=0;                                      // start at top
  digit[0]=0;                                       // start at 0
  while(1) {
    if (combos[depth]) {                            // if bits left
      unsigned int avail=combos[depth];             // save old
      combos[depth]=avail & (avail-1);              // remove lowest bit
      unsigned int bit=avail-combos[depth];         // get lowest bit
      digit[depth+1]=digit[depth]+mult[depth]*array[bit_val(bit)]; // get associated digit
      unsigned int rest=unused[depth]&(~bit);       // all remaining
      depth++;                                      // go to next digit
      if (depth!=length-1) {                        // not at bottom
        unused[depth]=combos[depth]=rest;           // try remaining
      } else {
        show(digit[depth]+array[bit_val(rest)]);    // print it
        depth--;                                    // stay on same level
      }
    } else {
      depth--;                                      // go back up a level
      if (depth < 0)
        break;                                      // all done
    }
  }
}

Algunos tiempos usando solo 1 a 9 con 1000 repeticiones:

• 15.00s Recursivo (modificado para contar del 1 al 9) desde https://.com/a/31828305/2963099
• Recursión de intercambio de 3.53s desde https://.com/a/31830671/2963099
• 2.74s siguiente Versión de permutación ( https://.com/a/31885811/2963099 )
• 2.34s Esta solución
• 1.66s versión recursiva desenrollada en EDITAR desde https://.com/a/31928246/2963099

Answer 6

Aquí hay un enfoque: comience con una serie de dígitos únicos, luego mezcle aleatoriamente:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int main( void )
{
  char digits[] = "123456789";

  srand( time( NULL ) );

  size_t i = sizeof digits - 1;
  while( i )
  {
    size_t j = rand() % i;
    char tmp = digits[--i];
    digits[i] = digits[j];
    digits[j] = tmp;
  }

  printf( "number is %s/n", digits );
  return 0;
}

Algunos resultados de muestra:

john@marvin:~/Development/snippets$ ./nine
number is 249316578
john@marvin:~/Development/snippets$ ./nine
number is 928751643
john@marvin:~/Development/snippets$ ./nine
number is 621754893
john@marvin:~/Development/snippets$ ./nine
number is 317529864

Tenga en cuenta que estas son cadenas de caracteres de dígitos decimales únicos, no valores numéricos; si desea el valor entero correspondiente, deberá realizar una conversión como

long val = strtol( digits, NULL, 10 );

Answer 7

Aquí hay un programa simple que imprimirá todas las permutaciones de un conjunto de caracteres. Puede convertirlo fácilmente para generar todos los números que necesita:

#include <stdio.h>

static int step(const char *str, int n, const char *set) {
    char buf[n + 2];
    int i, j, count;

    if (*set) {
        /* insert the first character from `set` in all possible
         * positions in string `str` and recurse for the next
         * character.
         */
        for (count = 0, i = n; i >= 0; i--) {
            for (j = 0; j < i; j++)
                buf[j] = str[j];
            buf[j++] = *set;
            for (; j <= n; j++)
                buf[j] = str[j - 1];
            buf[j] = ''/0'';
            count += step(buf, n + 1, set + 1);
        }
    } else {
        printf("%s/n", str);
        count = 1;
    }
    return count;
}

int main(int argc, char **argv) {
    int total = step("", 0, argc > 1 ? argv[1] : "123456789");
    printf("%d combinations/n", total);
    return 0;
}

Utiliza la recursividad pero no máscaras de bits y se puede usar para cualquier conjunto de caracteres. También calcula el número de permutaciones, por lo que puede verificar que produce permutaciones factoriales (n) para un conjunto de n caracteres.

Answer 8

Dada una matriz de números, es posible generar la próxima permutación de esos números con una función bastante simple (llamemos a esa función nextPermutation ). Si la matriz comienza con todos los números en orden, la función nextPermutation generará todas las permutaciones posibles en orden ascendente. Por ejemplo, este código

int main( void )
{
    int array[] = { 1, 2, 3 };
    int length = sizeof(array) / sizeof(int);

    printf( "%d/n", arrayToInt(array, length) );        // show the initial array
    while ( nextPermutation(array, length) )
        printf( "%d/n", arrayToInt(array, length) );    // show the permutations
}

generará esta salida

123
132
213
231
312
321

y si cambias la array a

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

entonces el código generará y mostrará todas las 362880 permutaciones de esos nueve números en orden ascendente.

La nextPermutation función de nextPermutation tiene tres pasos

1. comenzando desde el final de la matriz, encuentre el primer número (llámelo x ) seguido de un número mayor
2. comenzando desde el final de la matriz, encuentre el primer número (llámelo y ) que sea mayor que x , e intercambie x e y
3. y es ahora donde estaba x , y todos los números a la derecha de y están en orden descendente, cámbielos para que estén en orden ascendente

Permítanme ilustrar con un ejemplo. Supongamos que la matriz tiene los números en este orden

1 9 5 4 8 7 6 3 2

El primer paso sería encontrar el 4 . Como 8 7 6 3 2 están en orden descendente, el 4 es el primer número (comenzando desde el final de la matriz) seguido de un número mayor.

El segundo paso sería encontrar el 6 , ya que el 6 es el primer número (comenzando desde el final de la matriz) que es mayor que 4 . Después de intercambiar 4 y 6 la matriz se ve así

1 9 5 6 8 7 4 3 2

Observe que todos los números a la derecha del 6 están en orden descendente. Intercambiar el 6 y el 4 no cambió el hecho de que los últimos cinco números en la matriz están en orden descendente.

El último paso es intercambiar los números después del 6 para que estén todos en orden ascendente. Como sabemos que los números están en orden descendente, todo lo que tenemos que hacer es intercambiar el 8 con el 2 y el 7 con el 3 . La matriz resultante es

1 9 5 6 2 3 4 7 8

Entonces, dada cualquier permutación de los números, la función encontrará la próxima permutación simplemente intercambiando algunos números. La única excepción es la última permutación que tiene todos los números en orden inverso, es decir, 9 8 7 6 5 4 3 2 1 . En ese caso, el paso 1 falla y la función devuelve 0 para indicar que no hay más permutaciones.

Así que aquí está la nextPermutation función de nextPermutation

int nextPermutation( int array[], int length )
{
    int i, j, temp;

    // starting from the end of the array, find the first number (call it ''x'')
    // that is followed by a larger number
    for ( i = length - 2; i >= 0; i-- )
        if ( array[i] < array[i+1] )
            break;

    // if no such number was found (all the number are in reverse order)
    // then there are no more permutations
    if ( i < 0 )
        return 0;

    // starting from the end of the array, find the first number (call it ''y'')
    // that is larger than ''x'', and swap ''x'' and ''y''
    for ( j = length - 1; j > i; j-- )
        if ( array[j] > array[i] )
        {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            break;
        }

    // ''y'' is now where ''x'' was, and all of the numbers to the right of ''y''
    // are in descending order, swap them so that they are in ascending order
    for ( i++, j = length - 1; j > i; i++, j-- )
    {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    return 1;
}

Tenga en cuenta que la función nextPermutation funciona para cualquier conjunto de números (los números no necesitan ser secuenciales). Entonces, por ejemplo, si la matriz inicial es

int array[] = { 2, 3, 7, 9 };

entonces la función nextPermutation encontrará todas las permutaciones de 2,3,7 y 9.

Solo para completar, aquí está la función arrayToInt que se utilizó en la función main . Esta función es solo para fines de demostración. Se supone que la matriz solo contiene números de un solo dígito y no se molesta en comprobar si hay desbordamientos. Funcionará para un número de 9 dígitos siempre que un int sea ​​de al menos 32 bits.

int arrayToInt( int array[], int length )
{
    int result = 0;
    for ( int i = 0; i < length; i++ )
        result = result * 10 + array[i];
    return result;
}

Dado que parece haber cierto interés en el rendimiento de este algoritmo, aquí hay algunos números:

length= 2 perms= 2 (swaps= 1 ratio=0.500) time= 0.000msec length= 3 perms= 6 (swaps= 7 ratio=1.167) time= 0.000msec length= 4 perms= 24 (swaps= 34 ratio=1.417) time= 0.000msec length= 5 perms= 120 (swaps= 182 ratio=1.517) time= 0.001msec length= 6 perms= 720 (swaps= 1107 ratio=1.538) time= 0.004msec length= 7 perms= 5040 (swaps= 7773 ratio=1.542) time= 0.025msec length= 8 perms= 40320 (swaps= 62212 ratio=1.543) time= 0.198msec length= 9 perms= 362880 (swaps= 559948 ratio=1.543) time= 1.782msec length=10 perms= 3628800 (swaps= 5599525 ratio=1.543) time= 16.031msec length=11 perms= 39916800 (swaps= 61594835 ratio=1.543) time= 170.862msec length=12 perms=479001600 (swaps=739138086 ratio=1.543) time=2036.578msec

La CPU para la prueba fue un procesador Intel i5 de 2.5Ghz. El algoritmo genera alrededor de 200 millones de permutaciones por segundo, y toma menos de 2 milisegundos para generar todas las permutaciones de 9 números.

También es interesante que, en promedio, el algoritmo solo requiere alrededor de 1.5 swaps por permutación. La mitad del tiempo, el algoritmo simplemente intercambia los dos últimos números en la matriz. En 11 de 24 casos, el algoritmo realiza dos intercambios. Por lo tanto, solo en 1 de 24 casos el algoritmo necesita más de dos intercambios.

Finalmente, probé el algoritmo con las siguientes dos matrices.

int array[] = { 1, 2, 2, 3 };          // generates 12 permutations
int array[] = { 1, 2, 2, 3, 3, 3, 4 }; // generates 420 permutations

El número de permutaciones es el esperado y el resultado parece ser correcto, por lo que parece que el algoritmo también funciona si los números no son únicos.

Answer 9

En lugar de 10 variables, haría una sola variable con un conjunto de bits (y comprobable) para cada uno de los 10 dígitos. Entonces solo necesita una configuración de bucle (y prueba) del bit correspondiente a cada dígito. Algo como esto:

int ok = 1;
unsigned bits = 0;
int digit;
unsigned powers10 = 1;
for (digit = 0; digit < 10; ++digit) {
    unsigned bit = 1 << ((num / powers10) % 10);
    if ((bits & bit) != 0) {
        ok = 0;
        break;
    }
    bits |= bit;
    powers10 *= 10;
}
if (ok) {
    printf("%d/n", num);
}

Programa completo (descartando #include líneas innecesarias #include ):

#include <stdio.h>

int main(void)
{
    int indx;
    int num;

    for(indx = 123456789; indx <= 987654321; indx++)
    {
        num = indx;
        int ok = 1;
        unsigned bits = 0;
        int digit;
        unsigned powers10 = 1;
        for (digit = 0; digit < 9; ++digit) {
            unsigned bit = 1 << ((num / powers10) % 10);
            if ((bit == 1) || ((bits & bit) != 0)) {
                ok = 0;
                break;
            }
            bits |= bit;
            powers10 *= 10;
        }
        if (ok) {
            printf("%d/n", num);
        }
    }
    return 0;
}

OP aclaró su pregunta cuando me iba a trabajar, y no me había centrado en la falta de ceros solicitados. (la respuesta se actualiza ahora). Esto produce las combinaciones esperadas de 362880.

Sin embargo, hubo un comentario sobre una respuesta que es más rápida, lo que provoca un seguimiento. Hubo (contando esta) tres respuestas comparables. En un chequeo rápido:

• La respuesta de (que cuenta ceros y da 3265920 combinaciones):

real 0m0.951s user 0m0.894s sys 0m0.056s

• éste:

real 0m49.108s user 0m49.041s sys 0m0.031s

• La respuesta de @George André (que también produjo el número esperado de combinaciones):

real 1m27.597s user 1m27.476s sys 0m0.051s

Answer 10

Este es un ejemplo bastante típico de un problema relacionado con la combinatorics .

¡Hay exactamente 9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1 = 9! = 362880 números decimales de nueve dígitos, donde cada dígito aparece exactamente una vez, y cero no se utiliza en absoluto. Esto se debe a que hay nueve posibilidades para el primer dígito, ocho para el segundo, y así sucesivamente, ya que cada dígito se usa exactamente una vez.

Por lo tanto, puede escribir fácilmente una función, que incluya la semilla , 0 ≤ semilla <362880, que devuelva una de las combinaciones únicas, de modo que cada combinación corresponda exactamente a una semilla. Por ejemplo,

unsigned int unique9(unsigned int seed)
{
    unsigned char digit[9] = { 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U };
    unsigned int  result = 0U;
    unsigned int  n = 9U;
    while (n) {
        const unsigned int i = seed % n;
        seed = seed / n;
        result = 10U * result + digit[i];
        digit[i] = digit[--n];
    }
    return result;
}

La matriz de digit se inicializa en el conjunto de nueve dígitos hasta ahora no utilizados. i indica el índice de esa matriz, de modo que el digit[i] es el dígito real utilizado. Como se usa el dígito, se reemplaza por el último dígito en la matriz, y el tamaño de la matriz n se reduce en uno.

Algunos resultados de ejemplo:

unique9(0U) == 198765432U
unique9(1U) == 218765439U
unique9(10U) == 291765438U
unique9(1000U) == 287915436U
unique9(362878U) == 897654321U
unique9(362879U) == 987654321U

El orden impar de los resultados se debe a que los dígitos en la matriz de digit cambian de lugar.

20150826 editado: si desea la combinación de index (por ejemplo, en orden lexicográfico), puede usar el siguiente enfoque:

#include <stdlib.h>
#include <string.h>
#include <errno.h>

typedef unsigned long  permutation_t;

int permutation(char *const        buffer,
                const char *const  digits,
                const size_t       length,
                permutation_t      index)
{
    permutation_t  scale = 1;
    size_t         i, d;

    if (!buffer || !digits || length < 1)
        return errno = EINVAL;

    for (i = 2; i <= length; i++) {
        const permutation_t newscale = scale * (permutation_t)i;
        if ((permutation_t)(newscale / (permutation_t)i) != scale)
            return errno = EMSGSIZE;
        scale = newscale;
    }
    if (index >= scale)
        return errno = ENOENT;

    memmove(buffer, digits, length);
    buffer[length] = ''/0'';

    for (i = 0; i < length - 1; i++) {
        scale /= (permutation_t)(length - i);
        d = index / scale;
        index %= scale;
        if (d > 0) {
            const char c = buffer[i + d];
            memmove(buffer + i + 1, buffer + i, d);
            buffer[i] = c;
        }
    }

    return 0;
}

Si especifica digits en orden creciente, y 0 <= index < length! , entonces el buffer será la permutación que tenga el index valor más pequeño. Por ejemplo, si digits="1234" y length=4 , entonces index=0 producirá buffer="1234" , index=1 producirá buffer="1243" , y así sucesivamente, hasta que index=23 arroje buffer="4321" .

La implementación anterior definitivamente no está optimizada de ninguna manera. El bucle inicial es calcular el factorial, con detección de desbordamiento. Una forma de evitar eso es usar una matriz temporal size_t [length] , y completarla de derecha a izquierda de manera similar a unique9() más arriba; entonces, el rendimiento debería ser similar a unique9() más arriba, a excepción de los memmove() s que necesita (en lugar de swaps).

Este enfoque es genérico. Por ejemplo, si desea crear palabras de N caracteres donde cada carácter es único y / o utiliza solo caracteres específicos, el mismo enfoque proporcionará una solución eficiente.

Primero, divida la tarea en pasos.

Arriba, nos quedan n dígitos no utilizados en la matriz de digit[] , y podemos usar seed para elegir el siguiente dígito no utilizado.

i = seed % n; establece i en el resto ( módulo ) si la seed se dividiera por n . Por lo tanto, es un número entero i entre 0 y n-1 inclusive, 0 ≤ i < n .

Para eliminar la parte de seed que usamos para decidir esto, hacemos la división: seed = seed / n; .

Luego, agregamos el dígito a nuestro resultado. Debido a que el resultado es un entero, simplemente podemos agregar una nueva posición de dígito decimal (multiplicando el resultado por diez) y agregar el dígito al lugar menos significativo (como el nuevo dígito más a la derecha), usando result = result * 10 + digit[i] En C, la U al final de la constante numérica solo le dice al compilador que la constante no tiene signo (entero). (Los otros son L por long , UL por unsigned long , y si el compilador los admite, LL por long long y ULL por unsigned long long ).

Si estuviéramos construyendo una cadena, simplemente pondríamos el digit[i] en la siguiente posición en la matriz de caracteres e incrementaríamos la posición. (Para convertirlo en una cadena, solo recuerde poner un carácter nul al final de la cadena, ''/0'' , al final).

Luego, debido a que los dígitos son únicos, debemos eliminar el digit[i] de la matriz de digit[] . Hago esto reemplazando el digit[i] por el último dígito en la matriz, digit[n-1] , y decrementando el número de dígitos que quedan en la matriz, n-- , esencialmente recortando el último dígito. Todo esto se hace usando el digit[i] = digit[--n]; que es exactamente equivalente a

digit[i] = digit[n - 1];
n = n - 1;

En este punto, si n todavía es mayor que cero, podemos agregar otro dígito, simplemente repitiendo el procedimiento.

Si no queremos usar todos los dígitos, podríamos usar un contador separado (o comparar n con n - digits_to_use ).

Por ejemplo, para construir una palabra usando cualquiera de las 26 letras minúsculas ASCII usando cada letra como máximo una vez, podríamos usar

char *construct_word(char *const str, size_t len, size_t seed)
{
    char letter[26] = { ''a'', ''b'', ''c'', ''d'', ''e'', ''f'', ''g'', ''h'', ''i'',
                        ''j'', ''k'', ''l'', ''m'', ''n'', ''o'', ''p'', ''q'', ''r'',
                        ''s'', ''t'', ''u'', ''v'', ''w'', ''x'', ''y'', ''z'' };
    size_t n = 26;

    if (str == NULL || len < 1)
        return NULL;

    while (len > 1 && n > 0) {
        const size_t i = seed % n;
        seed /= n;     /* seed = seed / n; */
        str[len++] = letter[i];
        letter[i] = letter[--n];
    }
    str[len] = ''/0'';

    return str;
}

Llame a la función con str apuntando a una matriz de caracteres de al menos len caracteres, siendo seed el número que identifica la combinación, y llenará str con una cadena de hasta 26 o len-1 caracteres (lo que sea menor) donde cada letra minúscula aparece como máximo una vez.

Si el enfoque no le parece claro, por favor pregunte: me gustaría mucho intentar aclararlo.

Verá, se pierde una cantidad sorprendente de recursos (no solo electricidad, sino también tiempo de usuario humano) al usar algoritmos ineficientes, simplemente porque es más fácil escribir código lento e ineficiente, en lugar de resolver el problema en cuestión de una manera eficiente . Perdemos dinero y tiempo de esa manera. Cuando la solución correcta es tan simple como en este caso, y como dije, esto se extiende a un gran conjunto de problemas combinatorios como es, prefiero ver que los programadores tomen los quince minutos para aprenderlo y aplicarlo siempre que sea útil, en lugar de ver los desechos propagados y expandidos.

Muchas respuestas y comentarios giran en torno a generar todas esas combinaciones (y contarlas). Personalmente, no veo mucho uso en eso, porque el conjunto ya es bien conocido. En la práctica, normalmente desea generar, por ejemplo, pequeños subconjuntos (pares, trillizos o conjuntos más grandes) o conjuntos de subconjuntos que cumplan algunos criterios; por ejemplo, es posible que desee generar diez pares de dichos números, con cada número de nueve dígitos utilizado dos veces, pero no en un solo par. Mi enfoque de semilla lo permite fácilmente; en lugar de la representación decimal, trabaja con los valores de inicialización consecutivos (0 a 362879, inclusive).

Dicho esto, es sencillo generar (e imprimir) todas las permutations de una cadena dada en C:

#include <stdlib.h>
#include <stdio.h>

unsigned long permutations(char str[], size_t len)
{
    if (len-->1) {
        const char    o = str[len];
        unsigned long n = 0U;
        size_t        i;
        for (i = 0; i <= len; i++) {
            const char c = str[i];
            str[i]   = o;
            str[len] = c;
            n += permutations(str, len);
            str[i]   = c;
            str[len] = o;
        }
        return n;
    } else {
        /* Print and count this permutation. */
        puts(str);
        return 1U;
    }
}

int main(void)
{
    char          s[10] = "123456789";
    unsigned long result;

    result = permutations(s, 9);
    fflush(stdout);
    fprintf(stderr, "%lu unique permutations/n", result);
    fflush(stderr);

    return EXIT_SUCCESS;
}

La función de permutación es recursiva, pero su profundidad máxima de recursión es la longitud de la cadena. El número total de llamadas a la función es a ( N ), donde N es la longitud de la cadena y a ( n ) = n ⋅ a ( n -1) +1 (secuencia A002627 ), 623530 llamadas en este caso particular . En general, a ( n ) ≤ (1- e ) n !, Es decir, a ( n ) <1.7183 n !, Por lo que el número de llamadas es O ( N !), Factorial con respecto al número de elementos permutados. El cuerpo del bucle se repite una vez menos en comparación con las llamadas, 623529 veces aquí.

La lógica es bastante simple, usando el mismo enfoque de matriz que en el primer fragmento de código, excepto que esta vez la parte "recortada" de la matriz se usa realmente para almacenar la cadena permutada. En otras palabras, intercambiamos cada carácter que todavía queda con el siguiente carácter que se va a trimemd (o antepuesto a la cadena final), hacemos la llamada recursiva y restauramos los dos caracteres. Debido a que cada modificación se deshace después de cada llamada recursiva, la cadena en el búfer es la misma después de la llamada que antes. Como si nunca hubiera sido modificado en primer lugar.

La implementación anterior asume caracteres de un byte (y no funcionaría con, por ejemplo, secuencias UTF-8 multibyte correctamente). Si se van a usar caracteres Unicode, o caracteres en algún otro conjunto de caracteres multibyte, entonces se deben usar caracteres anchos en su lugar. Aparte del cambio de tipo, y cambiando la función para imprimir la cadena, no se necesitan otros cambios.

Answer 11

Hay muchos fragmentos largos de código aquí. Es mejor pensar más y codificar menos.

Nos gustaría generar cada posibilidad exactamente una vez sin esfuerzo desperdiciado. Resulta que esto es posible con solo una cantidad constante de esfuerzo por dígito emitido.

¿Cómo harías esto sin código? Obtenga 10 tarjetas y escriba los dígitos del 0 al 9 en ellas. Dibuja una fila de 9 cuadrados en tu mesa. Toma una carta. Póngalo en el primer cuadrado, otro en el segundo, etc. Cuando haya elegido 9, tendrá su primer número. Ahora retire la última tarjeta y reemplácela con cada alternativa posible. (Solo hay 1 en este caso). Cada vez que se llenan todos los cuadrados, tiene otro número. Cuando hayas hecho todas las alternativas para el último cuadrado, hazlo para los últimos 2. Repite con los últimos 3, etc., hasta que hayas considerado todas las alternativas para todos los cuadros.

Escribir un programa sucinto para hacer esto se trata de elegir estructuras de datos simples. Use una matriz de caracteres para la fila de 9 cuadrados.

Use otra matriz para el conjunto de tarjetas. Para eliminar un elemento del conjunto de tamaño N almacenado en una matriz A [0 .. N-1], utilizamos un viejo truco. Digamos que el elemento que desea eliminar es A [I]. Guarde el valor de A [I] a un lado. Luego copie el último elemento A [N-1] "abajo", sobrescribiendo A [I]. El nuevo conjunto es A [0 .. N-2]. Esto funciona bien porque no nos importa el orden en un conjunto.

El resto es usar el pensamiento recursivo para enumerar todas las alternativas posibles. Si sé cómo encontrar todas las selecciones de un conjunto de caracteres de tamaño M en una cadena de tamaño N, para obtener un algoritmo, simplemente seleccione cada personaje posible para la primera posición de la cadena, luego vuelva a seleccionar el resto del N-1 caracteres del conjunto restante de tamaño M-1. Obtenemos una buena función de 12 líneas:

#include <stdio.h>

// Select each element from the given set into buf[pos], then recur
// to select the rest into pos+1... until the buffer is full, when
// we print it.
void select(char *buf, int pos, int len, char *set, int n_elts) {
  if (pos >= len)
    printf("%.*s/n", len, buf);  // print the full buffer
  else
    for (int i = 0; i < n_elts; i++) {
      buf[pos] = set[i];         // select set[i] into buf[pos]
      set[i] = set[n_elts - 1];  // remove set[i] from the set
      select(buf, pos + 1, len, set, n_elts - 1); // recur to pick the rest
      set[n_elts - 1] = set[i];  // undo for next iteration
      set[i] = buf[pos];
    }
}

int main(void) {
  char buf[9], set[] = "0123456789";
  select(buf, 0, 9, set, 10); // select 9 characters from a set of 10
  return 0;
}

No mencionaste si está bien poner un cero en la primera posición. Supongamos que no lo es. Como entendemos bien el algoritmo, es fácil evitar seleccionar cero en la primera posición. Simplemente omita esa posibilidad observando que !pos en C tiene el valor 1 si pos es 0 y 0. Si no le gusta este idioma un poco oscuro, intente (pos == 0 ? 1 : 0) como un reemplazo más legible:

#include <stdio.h>

void select(char *buf, int pos, int len, char *set, int n_elts) {
  if (pos >= len)
    printf("%.*s/n", len, buf);
  else
    for (int i = !pos; i < n_elts; i++) {
      buf[pos] = set[i];
      set[i] = set[n_elts - 1];
      select(buf, pos + 1, len, set, n_elts - 1);
      set[n_elts - 1] = set[i];
      set[i] = buf[pos];
    }
}

int main(void) {
  char buf[9], set[] = "0123456789";
  select(buf, 0, 9, set, 10);
  return 0;
}

Answer 12

La recursión funciona muy bien aquí.

#include <stdio.h>

void uniq_digits(int places, int prefix, int mask) {
  if (!places) {
    printf("%d/n", prefix);
    return;
  }
  for (int i = 0; i < 10; i++) {
    if (prefix==0 && i==0) continue;
    if ((1<<i)&mask) continue;
    uniq_digits(places-1, prefix*10+i, mask|(1<<i)); 
  }
}

int main(int argc, char**argv) {
  uniq_digits(9, 0, 0);
  return 0;
}

Answer 13

Puede usar una máscara para establecer banderas, ya que las banderas que están en un dígito ya se han visto en el número o no. Me gusta esto:

int mask = 0x0, j;

for(j= 1; j<=9; j++){
    if(mask & 1<<(input%10))
        return 0;
    else
        mask |= 1<<(input%10);
    input /= 10;
}
return !(mask & 1);

El programa completo:

    #include <stdio.h>

int check(int input)
{
    int mask = 0x0, j;

    for(j= 1; j<=9; j++){
        if(mask & 1<<(input%10))
            return 0;
        else
            mask |= 1<<(input%10);
        input /= 10;
    }
    /* At this point all digits are unique
     We''re not interested in zero, though */
    return !(mask & 1);
}

int main()
{
    int indx;
    for( indx = 123456789; indx <=987654321; indx++){
        if( check(indx) )
            printf("%d/n",indx);
    }
}

Editado ...

O podría hacer lo mismo con una matriz:

int check2(int input)
{
    int j, arr[10] = {0,0,0,0,0,0,0,0,0,0};

    for(j=1; j<=9; j++) {
        if( (arr[input%10]++) || (input%10 == 0) )
            return 0;
        input /= 10;
    }
    return 1;
}

Answer 14

Recomiendo la answer Nominal Animal, pero si solo está generando este valor para poder imprimirlo, puede eliminar parte del trabajo y al mismo tiempo obtener una rutina más genérica utilizando el mismo método:

char *shuffle( char *digit, int digits, int count, unsigned int seed )
{
    //optional: do some validation on digit string
    //  ASSERT(digits == strlen(digit));
    //optional: validate seed value is reasonable
    //  for(unsigned int badseed=1, x=digits, y=count; y > 0; x--, y--)
    //      badseed *= x;
    //  ASSERT(seed < badseed);

    char *work = digit;
    while(count--)
    {
        int i = seed % digits;
        seed /= digits--;
        unsigned char selectedDigit = work[i];
        work[i] = work[0];
        work[0] = selectedDigit;
        work++;
    }
    work[0] = 0;

    //seed should be zero here, else the seed contained extra information
    return digit;
}

Este método es destructivo en los dígitos pasados, que en realidad no tienen que ser numéricos o únicos para el caso.

En caso de que desee que los valores de salida se generen en orden creciente ordenado, eso es un poco más de trabajo:

char *shuffle_ordered( char *digit, int digits, int count, unsigned int seed )
{
    char *work = digit;
    int doneDigits = 0; 
    while(doneDigits < count)
    {
        int i = seed % digits;
        seed /= digits--;
        unsigned char selectedDigit = work[i];
        //move completed digits plus digits preceeding selectedDigit over one place
        memmove(digit+1,digit,doneDigits+i);
        digit[0] = selectedDigit;
        work++;
    }
    work[0] = 0;

    //seed should be zero here, else the seed contained extra information
    return digit;
}

En cualquier caso se llama así:

for(unsigned int seed = 0; seed < 16*15*14; ++seed)
{
    char work[] = "0123456789ABCDEF";
    printf("seed=%d -> %s/n",shuffle_ordered(work,16,3,seed));
}

Esto debería imprimir una lista ordenada de valores hexadecimales de tres dígitos sin dígitos duplicados:

seed 0 -> 012
seed 1 -> 013
...
seed 3358 -> FEC
seed 3359 -> FED

No sé qué estás haciendo realmente con estas secuencias de dígitos cuidadosamente elaboradas. Si algún ingeniero de mantenimiento pobre va a tener que venir detrás de usted para corregir algún error, recomiendo la versión ordenada, ya que es mucho más fácil para un humano convertir la semilla de / al valor de secuencia.

Answer 15

Revisa este código.

    #include<stdio.h>

    //it can be done by recursion

    void func(int *flag, int *num, int n){  //take ''n'' to count the number of digits
        int i;
        if(n==9){                           //if n=9 then print the number
            for(i=0;i<n;i++)
                printf("%d",num[i]);
            printf("/n");
        }
        for(i=1;i<=9;i++){

            //put the digits into the array one by one and send if for next level

            if(flag[i-1]==0){
                num[n]=i;
                flag[i-1]=1;
                func(flag,num,n+1);
                flag[i-1]=0;
            }
        }
    }

    //here is the MAIN function
    main(){

        int i,flag[9],num[9];
        for(i=0;i<9;i++)        //take a flag to avoid repetition of digits in a number
            flag[i]=0;          //initialize the flags with 0

        func(flag,num,0);       //call the function

        return 0;
    }

Si usted tiene alguna pregunta no dude en preguntar.

Answer 16

EDITAR: Después de un análisis más profundo, más desenrollamiento de recursión y solo iterar en bits establecidos dio como resultado una mejora significativa, en mis pruebas aproximadamente CINCO veces más rápido . Esto se probó con OUTPUT UNSET para comparar la velocidad del algoritmo, no la salida de la consola, el punto de inicio es uniq_digits9 :

int counter=0;
int reps=0;

void show(int x)
{
#ifdef OUTPUT
    printf("%d/n", x);
#else
    counter+=x;
    ++reps;
#endif
}

int bit_val(unsigned int v)
{
  static const int MultiplyDeBruijnBitPosition2[32] =
  {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  return MultiplyDeBruijnBitPosition2[(unsigned int)(v * 0x077CB531U) >> 27];
}

void uniq_digits1(int prefix, unsigned int used) {
  show(prefix*10+bit_val(~used));
}

void uniq_digits2(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits1(base+bit_val(bit), used|bit);
  }
}

void uniq_digits3(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits2(base+bit_val(bit), used|bit);
  }
}

void uniq_digits4(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits3(base+bit_val(bit), used|bit);
  }
}

void uniq_digits5(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits4(base+bit_val(bit), used|bit);
  }
}

void uniq_digits6(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits5(base+bit_val(bit), used|bit);
  }
}

void uniq_digits7(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits6(base+bit_val(bit), used|bit);
  }
}

void uniq_digits8(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits7(base+bit_val(bit), used|bit);
  }
}

void uniq_digits9() {
  unsigned int used=~((1<<10)-1); // set all bits except 0-9
#ifndef INCLUDE_ZEROS
  used |= 1;
#endif
  for (int i = 1; i < 10; i++) {
    unsigned int bit=1<<i;
    uniq_digits8(i,used|bit);
  }
}

Breve explicación :

Hay 9 dígitos y el primero no puede comenzar con cero, por lo que el primer dígito puede ser del 1 al 9, el resto puede ser del 0 al 9

Si tomamos un número, X y lo multiplicamos por 10, se desplaza un lugar. Entonces, 5 se convierte en 50. Agregue un número, diga 3 para hacer 53, y luego multiplique por 10 para obtener 520, y luego agregue 2, y así sucesivamente para los 9 dígitos.

Ahora se necesita algo de almacenamiento para realizar un seguimiento de los dígitos que se usaron para que no se repitan. 10 variables de verdadero / falso se podrían utilizar: used_0_p , used_1_P , .... Pero, que es ineficiente, por lo que pueden ser colocados en una matriz: used_p[10] . Pero luego tendría que copiarse cada vez antes de hacer una llamada al siguiente lugar para que pueda restablecerlo para el siguiente dígito, de lo contrario, una vez que se llenen todos los lugares la primera vez, la matriz sería verdadera y no se podrían calcular otras combinaciones.

Pero hay una mejor manera. Use bits de an int como la matriz. X & 1 para el primero, X & 2 , X & 4 , X & 8 , etc. Esta secuencia se puede representar como (1<<X) o tomar el primer bit y desplazar por encima de X veces.

& se usa para probar bits, | se usa para configurarlos. En cada ciclo probamos si se utilizó el bit (1<<i)&used y omitimos si lo fue. En el siguiente lugar, cambiamos los dígitos para cada dígito prefix*10+i y establecemos ese dígito como se usa used|(1<<i)

Explicación de bucles en el EDIT

El bucle calcula Y & (Y-1) cuál pone a cero el bit de ajuste más bajo. Al tomar el original y restar el resultado, la diferencia es el bit más bajo. Esto se repetirá tantas veces como haya bits: 3.265.920 veces en lugar de 900.000.000 de veces. Cambiar de usado a no usado es solo el ~ operador, y dado que la configuración es más eficiente que la desarmado, tenía sentido cambiar

El paso del poder de dos a su log2 se tomó de: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog . Este sitio también detalla el mecanismo de bucle: https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

Mover original al fondo:

Esto es demasiado largo para un comentario, pero esta respuesta se puede hacer algo más rápido al eliminar el manejo de cero de la función: (Ver edición para obtener la respuesta más rápida)

void uniq_digits(int places, int prefix, int used) {
  if (!places) {
    printf("%d/n", prefix);
    return;
  }
  --places;
  int base=prefix*10;
  for (int i = 0; i < 10; i++)
  {
    if ((1<<i)&used) continue;
    uniq_digits(places, base+i, used|(1<<i));
  }
}

int main(int argc, char**argv) {
  const int num_digits=9;

  // unroll top level to avoid if for every iteration
  for (int i = 1; i < 10; i++)
  {
    uniq_digits(num_digits-1, i, 1 << i);
  }

  return 0;
}