logo标签列表

尝试生成每个数字都不同的9位数

crandomunique
33

我正在尝试获取所有具有唯一数字的九位数。我的第一个方法似乎过于复杂，写起来很繁琐。

#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);
        }
    }
}

那只是将第一个数字与其余数字进行比较。我还需要做很多次才能比较其他数字。有更好的方法吗？

6
使用数组...... - Maroun
2
当你有很多变量命名为d1，d2等等时，这应该是将它们转换为数组的重要提示。 - M Oehm
2
我甚至认为你目前的方法不正确，因为第二位和第三位数字可以相同，第二位和第四位、第二位和第五位......第八位和第九位也可以相同。 - M. Shaw
3
把它变成字符串"123456789"的排列，然后将该字符串转换为一个数字，您觉得如何？ - Matthias
4
你是包括0还是只有1-9？ - Paul R
显示剩余4条评论
16个回答
5

这里有一个有点丑但是非常快的解决方案，它使用了嵌套的for循环。

#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;
}

使用一些宏来实现同样的功能。

#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;
}

我相信有更好的方法来编写这些宏，但这是我能想到的。

5
编辑： 经过进一步分析，更多的递归展开以及只迭代设置位会显著提高性能，在我的测试中，速度大约快五倍。这是使用OUTPUT未设置进行测试，以比较算法速度而不是控制台输出，起始点为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);
  }
}

简要说明:

这里有9个数字，第一个数字不能以零开头，因此第一个数字可以是1到9，其余数字可以是0到9。

如果我们取一个数字X并将其乘以10，则它会向左移动一位。所以，5变成了50。加上一个数字，比如3，使其成为53，然后将其乘以10得到520，然后再加上2，以此类推，直到所有9个数字都填满。

现在需要一些存储空间来跟踪使用的数字，以便它们不会重复出现。可以使用10个布尔变量：used_0_p，used_1_P，...但这是低效的，因此它们可以放置在数组中：used_p[10]。但是，在进行下一个数字的调用之前，它需要被复制，以便为下一个数字重置它，否则一旦所有位置第一次填满，数组就会全部为true，无法计算其他组合。

但是，有一种更好的方法。使用int的位作为数组。第一个使用X & 1，第二个使用X & 2，X & 4，X & 8等。这个序列可以表示为(1<<X)或者取第一个位并将其向左移动X次。 &用于测试位，|用于设置位。在每个循环中，我们测试位是否被使用(1<<i)&used，如果被使用则跳过。在下一个位置，我们为每个数字prefix*10+i移动数字，并将该数字设置为已使用used|(1<<i) < p>编辑中循环的解释

该循环计算Y & (Y-1)，将最低位设为零。通过将原始值减去结果，差值即为最低位。循环次数仅为位数：3,265,920次，而非900,000,000次。从已使用到未使用只需要使用~运算符，且由于设置比取消设置更有效，因此翻转是有意义的。
从2的幂到其log2的转换来自于：https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog。该网站还详细介绍了循环机制：https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 将原始值移到底部： 这段文字有点长，但是这个答案可以通过从函数中删除零处理来使得速度更快：（请参见编辑以获取最快的答案）
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;
}
问题下面的评论表明0不是结果中有效的数字。只有1-9是需要的。 - Speed8ump
添加了#ifdef以包含0s。 - Glenn Teitelbaum
5

一种简单的方法是创建一个包含九个不同值的数组，对其进行洗牌，然后打印出洗牌后的数组。根据需要重复此过程多次。例如，可以使用标准的rand()函数作为洗牌的基础...

#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;
}

这将在 stdout 上打印多行，每行包括9个不同的数字。需要注意的是这并不能防止重复。

0
创建一个包含10个元素的列表，值为0-9。使用rand()函数从当前列表长度中随机取出元素，直到你获得所需数量的数字。
0

使用位运算广泛的迭代版本

请注意，array可以更改为任何类型，并以任何顺序设置 这将按给定顺序“计数”数字

有关更多说明，请查看我的第一个答案（它不太灵活，但速度更快）https://dev59.com/ClwZ5IYBdhLWcg3wINPQ#31928246

为了使其成为迭代版本，需要使用数组在每个级别上保持状态

这也经过了相当多的优化，以优化优化器无法解决的地方

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
    }
  }
}

使用1到9进行1000次重复的一些时间记录：

@这里是通用的迭代版本，它比我的另一个版本慢两倍，但是给你。 - Glenn Teitelbaum
你现在是在比较苹果和橘子。你的函数会在一次调用中输出所有可能的值，而其他解决方案只会输出一个值。你怎么没有注意到这一点呢？即使忽略这一点，我也严重怀疑你的测量方法是否正确。 - this
编写一个函数，它接受一个数组和其长度，就像nextPermutation函数一样，并将下一个值写入数组并返回。然后尝试进行比较。 - this
@this是生成所有的OP，递归生成所有，交换代码生成所有，nextPermutation有一个生成所有的主函数。如果你怀疑我的方法，请运行它。没有要求生成下一个，尽管这很聪明。我的展开递归仍然是解决OP需求最快的方法，在C++中使用模板和std::bitset可以更快，但这是C。 - Glenn Teitelbaum
你的函数可能是最快的，根据你的测量，但是如果你定义了输出（OUTPUT），那么该函数就不会返回或写入任何值。结果只是丢失了。嗯，其他函数似乎每次调用时都返回一个结果。这个事实以及每个其他函数都可以被修改，使其在内部计算每个值而不是在循环中调用以产生额外开销，使你的条目无效。再见。 - this
不过这样也好，非常感谢你，我很享受将算法转换为迭代的挑战，并对其进行优化。 - Glenn Teitelbaum
0
有点晚来的派对，但非常快（这里只有30毫秒）...
#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;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接