尝试使用每个唯一的数字生成9位数字

我想获得9位数字，都有唯一的数字。 我的第一个方法似乎有点太复杂，写起来会很乏味。

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

那只是比较第一个数字和其余的数字。 我将不得不做更多的比较其他数字。 有一个更好的方法吗？

Answer 1

这是涉及组合的问题的一个非常典型的例子。

正好有9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1= 9！ = 362880个九位十进制数字，每个数字只出现一次，根本不使用零。 这是因为第一个数字有九个可能性，第二个数字有八个可能性，以此类推，因为每个数字只用一次。

所以，你可以很容易地写一个函数，该函数接受种子 0≤seed <362880，返回一个唯一的组合，这样每个组合恰好对应一个种子。 例如，

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

digit数组被初始化为九个迄今未使用的数字的集合。 i指出该数组的索引，所以digit[i]是实际使用的数字。 由于使用了数字，所以它被数组中的最后一位数字所取代，并且数组n的大小减1。

一些示例结果：

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

结果的奇数顺序是因为digit数组开关中的digit 。

编辑20150826：如果你想index th组合（说，按照字典顺序），你可以使用以下的方法：

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

如果您按递增顺序指定digits ，并且0 <= index < length! ，那么buffer将是index th值最小的排列。 例如，如果digits="1234"和length=4 ，那么index=0将产生buffer="1234" ， index=1将产生buffer="1243" ，依此类推，直到index=23将产生buffer="4321" 。

上面的实现绝对不是以任何方式优化的。 初始循环是计算阶乘，用溢出检测。 一种避免使用临时size_t [length]数组的方法，并且类似于上面的unique9() ，从右到左填充它; 那么，性能应该与上面的unique9()类似，除了需要的memmove() （而不是交换）之外。

---

这种方法是通用的。 例如，如果要创build每个字符都是唯一的N个字符的字词，并且/或者只使用特定字符，则相同的方法将产生有效的解决scheme。

首先，将任务分成几个步骤。

上面，我们在digit[]数组中剩下了n未使用的数字，我们可以使用seed来select下一个未使用的数字。

i = seed % n; 如果将seed除以n则将i设置为余数（ 模数 ）。 因此，是0和n-1含）之间的整数， 0 ≤ i < n 。

为了除去我们用来决定这个的seed的部分，我们进行分割： seed = seed / n; 。

接下来，我们将数字添加到我们的结果。 因为结果是一个整数，所以我们可以添加一个新的十进制数位（通过乘以十），并将数字添加到最不重要的位置（作为新的最右边的数字），使用result = result * 10 + digit[i] 。 在C中，数字常量末尾的U只是告诉编译器常量是无符号的（整数）。 （其他的long为L ， UL为unsigned long ，如果编译器支持它们， LL long long ， ULL unsigned long long 。）

如果我们构造一个string，我们只需要把digit[i]放到char数组中的下一个位置，然后增加位置。 （要把它变成一个string，只要记住把一个string结尾的空字符'\0'放在最后）。

接下来，由于数字是唯一的，我们必须从digit[]数组中删除digit[i] 。 我通过用数组中的最后一位digit[n-1]replacedigit[i] ，然后递减数组中剩余的位数n--来实现这n-- ，从本质上n--最后一位数字。 所有这些都是通过使用digit[i] = digit[--n]; 这完全等同于

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

此时，如果n仍然大于零，我们可以添加另一个数字，只需重复该过程即可。

如果我们不想使用所有的数字，我们可以使用一个单独的计数器（或比较n到n - digits_to_use ）。

例如，要使用最多一次使用每个字母的26个ASCII小写字母中的任意一个来构造一个单词，我们可以使用

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

使用str指向至less为len字符的字符数组来调用函数，其中seed是标识组合的数字，它将填充string长度为26或len-1字符（以较less者为准）的str每个小写字母至多出现一次。

如果这个方法看起来不太清楚，请问：我非常想尝试澄清。

你会发现，通过使用低效率的algorithm会损失大量的资源（不仅仅是电力，而且还有人类的用户时间），只是因为编写速度慢，效率低下的代码更容易 ，而不是真正以高效的方式解决问题。 我们浪费金钱和时间。 当正确的解决scheme和这个例子一样简单的时候，就像我说的那样，这个问题会延伸到一大堆组合问题，我宁愿看到程序员花了十五分钟时间来学习它，只要有用，而不是看到浪费传播和扩大。

---

许多答案和评论围绕着生成所有这些组合（并对它们进行计数）。 我个人并没有看到太多的用处，因为这个组合已经是众所周知的了。 在实践中，你通常想要生成例如小的子集 – 对，三元组或者更大的集合 – 或者满足一些标准的子集集合; 例如，您可能希望生成十对这样的数字，每个九位数字使用两次，但不是一对。 我的种子方法容易， 而不是十进制表示法，而是使用连续的种子值（0到362879，含）。

也就是说，直接生成（并打印）C中给定string的所有排列 ：

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

置换函数是recursion的，但其最大recursion深度是string长度。 函数的调用总数为（ N ），其中N是string的长度，并且a （ n ）= n · a （ n -1）+1（序列A002627 ），623530在这种特定情况下调用。 一般来说， a （ n ）≤（1- e ） n ！，即a （ n ）<1.7183 n ！，所以调用次数为O （ N ！ 循环体与迭代次数相比less了一倍，这里是623529次。

这个逻辑非常简单，使用与第一个代码片段相同的数组方法，除了这次数组的“trim off”部分实际上用于存储排列的string。 换句话说，我们将每个仍然留下的字符与下一个字符进行交换（或者添加到最后一个string前面），进行recursion调用，然后恢复这两个字符。 因为在每次recursion调用之后，每个修改都被撤消，所以在调用之后，缓冲区中的string与之前的一样。 就好像它从来没有被修改过。

上面的实现确实假定了一个字节的字符（并且不能正确使用例如多字节的UTF-8序列）。 如果要使用Unicode字符或其他多字节字符集中的字符，则应该使用宽字符。 除了types改变以及改变打印string的function之外，不需要其他改变。

Answer 2

给定一组唯一的数字，可以用一个相当简单的函数生成这些数字的下一个排列（让我们称之为nextPermutation ）。 如果数组以sorting顺序的所有数字开始，那么nextPermutation函数将按升序生成所有可能的排列。 例如，这个代码

 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 } 

会生成这个输出

 123 132 213 231 312 321 

如果你改变array

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

那么代码将按升序生成并显示这9个数字的所有362880个排列。

---

nextPermutation函数有三个步骤

1. 从数组的末尾开始，find第一个数字（称之为x ），后面跟着一个更大的数字
2. 从数组的末尾开始，find比x大的第一个数字（称为y ），并交换x和y
3. y现在是x所在的位置， y右边的所有数字都是按降序排列的，交换它们使它们按升序排列

让我以一个例子来说明。 假设数组按这个顺序有数字

 1 9 5 4 8 7 6 3 2 

第一步将find4 。 由于8 7 6 3 2按降序排列，因此4是第一个数字（从数组末尾开始），后面跟着一个更大的数字。

第二步将find6 ，因为6是第一个数字（从数组的末尾开始）大于4 。 交换4和6 ，数组看起来像这样

 1 9 5 6 8 7 4 3 2 

请注意， 6中右边的所有数字都是按降序排列的。 交换6和4并没有改变数组中最后五个数字按降序排列的事实。

最后一步是在6之后交换数字，以便它们全部按升序排列。 既然我们知道这个数字是从大到小，我们只需要把8与2交换，把7与3交换。 结果数组是

 1 9 5 6 2 3 4 7 8 

所以，给定任何数字的排列，函数将通过交换几个数字来find下一个排列。 唯一的例外是所有数字以相反顺序排列的最后的排列，即9 8 7 6 5 4 3 2 1 。 在这种情况下，第1步失败，函数返回0表示没有更多的排列。

---

所以这是下一个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; } 

请注意， nextPermutation函数适用于任何数字数组，只要数字是唯一的。 因此，例如，如果你从下面的数组开始

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

那么下一个nextPermutation函数将会find所有2,3,7和9的排列。

---

为了完整arrayToInt ，这里是arrayToInt函数中使用的arrayToInt函数。 此function仅用于演示目的。 它假定数组只包含单个数字的数字，并且不打扰检查溢出。 如果int至less为32位，它将工作9位数字。

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

---

由于似乎对这个algorithm的性能有一些兴趣，下面是一些数字：

长度= 2平方厘米= 2（交换= 1比率= 0.500）时间= 0.000毫秒
长度= 3每平方米= 6（交换= 7比= 1.167）时间= 0.000毫秒
长度= 4平方厘米= 24（交换= 34比率= 1.417）时间= 0.000毫秒
长度= 5平方厘米= 120（交换= 182比率= 1.517）时间= 0.001毫秒
长度= 6平方厘米= 720（交换= 1107比= 1.538）时间= 0.004毫秒
长度= 7每平方米= 5040（交换= 7773比率= 1.542）时间= 0.025毫秒
长度= 8每毫米= 40320（交换= 62212比率= 1.543）时间= 0.198毫秒
长度= 9 perms = 362880（交换= 559948比= 1.543）时间= 1.782msec
长度= 10 perms = 3628800（交换= 5599525比= 1.543）时间= 16.031msec
长度= 11 perms = 39916800（交换= 61594835比率= 1.543）时间= 170.862msec
长度= 12 perms = 479001600（交换= 739138086比率= 1.543）时间= 2036.578msec

testing的CPU是2.5Ghz Intel i5处理器。 该algorithm每秒生成约2亿个置换，并且花费不到2毫秒来生成9个数字的所有置换。

另外感兴趣的是，algorithm平均每个置换只需要大约1.5次交换。 一半的时间，algorithm只是交换arrays中的最后两个数字。 在24个案例中，有11个algorithm做了两次交换。 所以在24个案例中只有一个algorithm需要两次以上的交换。

最后，我尝试了以下两个数组的algorithm

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

排列的数量如预期的那样，并且输出看起来是正确的，所以如果数字不是唯一的，algorithm也可以工作，但是我没有保证。

Answer 3

recursion在这里很好地工作。

 #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 4

这是一个简单的程序，将打印一组字符的所有排列。 您可以轻松地将其转换为您需要的所有数字：

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

它使用recursion而不是位掩码，可以用于任何字符集。 它还计算排列的数量，因此您可以validation它为一组n个字符生成阶乘（n）排列。

Answer 5

这里有很多很长的代码。 最好多思考，less编码。

我们希望每一个可能性都可以精确地产生一次，而不会浪费精力。 事实certificate这是可能的，只有每个数字发出的努力量不变。

你怎么做这个没有代码？ 获得10张卡片，并在其上写入数字0到9。 在桌面上画一排9格。 选一张卡。 把它放在第一个方块，第二个方块，等等。当你select了9，你有你的第一个号码。 现在删除最后一张卡，并replace每个可能的替代品。 （在这种情况下只有1个）每次填满所有的方块，你都有另一个数字。 当你完成了最后一个方块的所有select时，在最后一个方块上做所有的select。重复上一个3，等等，直到你考虑了所有方块的所有select。

编写一个简洁的程序来做到这一点是关于select简单的数据结构。 对9平方的行使用一个字符数组。

使用另一个arrays的卡组。 为了从存储在数组A [0..N-1]中的大小为N的集合中移除一个元素，我们使用一个古老的技巧。 说你想删除的元素是A [I]。 将A [I]的值保存到一边。 然后复制最后一个元素A [N-1]“向下”，覆盖A [I]。 新的集合是A [0..N-2]。 这工作正常，因为我们不关心在一个集合的顺序。

剩下的就是用recursion思想来列举所有可能的select。 如果我知道如何从大小为M的字符集中find所有select的string为大小为N的string，那么只要为第一个string位置select每个可能的字符，然后再select其余的N-1来自剩下的大小为M-1的字符。 我们得到一个很好的12行function：

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

你没有提到在第一个位置放置零是否可以。 假设它不是。 由于我们很好地理解algorithm，因此很容易避免将零点select到第一个位置。 如果pos是0和0，那么在C中的pos值为1.如果你不喜欢这个稍微模糊的成语，试试(pos == 0 ? 1 : 0)作为一个更可读的replace：

 #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 6

你可以使用一个掩码来设置标志，标志是否已经在数字中看到了一个数字。 喜欢这个：

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

完整的程序：

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

编辑…

或者你可以对数组做同样的事情：

 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 7

这里有一个方法 – 从一个唯一的数字开始，然后随机洗牌：

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

一些示例输出：

 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 

请注意，这些是唯一十进制数字的string ，而不是数字值; 如果你想要相应的整数值，你需要做一个类似的转换

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

Answer 8

而不是10个variables，我会为10个数字中的每一个设置一个variables（可testing）。 那么你只需要一个循环设置（和testing）对应于每个数字的位。 像这样的东西：

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

完整的程序（丢弃不必要的#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澄清了他的问题，而我没有把注意力集中在要求的零点上。 （响应现在更新）。 这产生了预期的362880个组合。

然而 – 有一个回应是最快的，这提示了后续的评论。 有（计算这一个）三个类似的答案。 快速检查：

• @Paul Hankin的答案（计算零和3265920的组合）：

    真正的0m0.951s
    用户0m0.894s
     sys 0m0.056s

• 这个：

    真0m49.108s
    用户0m49.041s
     sys 0m0.031s

• 乔治·安德烈的回答（也产生了预期的组合数量）：

     真正的1m27.597s
     用户1m27.476s
      sys 0m0.051s

Answer 9

检查这个代码。

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

如果您有任何问题随时问。

Answer 10

我推荐Nominal Animal的答案 ，但是如果你只是生成这个值，所以你可以打印出来，你可以消除一些工作，同时使用相同的方法得到一个更通用的例程：

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

这个方法对传入的数字是破坏性的，实际上并不一定是数字，也不是唯一的。

如果您希望按照sorting的递增顺序生成的输出值稍微多一点，

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

无论哪种情况，都是这样调用的：

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

这应该打印出一个三位hex值的有序列表，没有重复的数字：

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

我不知道你用这些精心打造的数字序列究竟在做什么 。 如果一些可怜的维护工程师不得不跟随你来修复一些bug，我推荐使用有序的版本，因为人类将种子从序列值转换成序列更容易。

Answer 11

这是一个有点丑陋，但非常快速的解决scheme，使用嵌套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; } 

Same thing using some 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; } 

I am sure there are better ways to write those macros, but that is what I could think of.

Answer 12

A simple way is to create an array with nine distinct values, shuffle it, and print the shuffled array. Repeat as many times as needed. For example, using the standard rand() function as a basis for shuffling …

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

This prints a number of lines to stdout , each with 9 unique digits. Note that this does not prevent duplicates.

Answer 13

EDIT: After further analysis, more recursion unrolling and only iterating on set bits resulted in significant improvement, in my testing roughly FIVE times as fast . This was tested with OUTPUT UNSET to compare algorithm speed not console output, start point is 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); } } 

Brief explanation :

There are 9 digits and the first cannot start with zero, so the first digit can be from 1 to 9, the rest can be 0 to 9

If we take a number, X and multiply it by 10, it shifts one place over. So, 5 becomes 50. Add a number, say 3 to make 53, and then multiply by 10 to get 520, and then add 2, and so on for all 9 digits.

Now some storage is needed to keep track of what digits were used so they aren't repeated. 10 true/false variables could be used: used_0_p , used_1_P , …. But, that is inefficient, so they can be placed in an array: used_p[10] . But then it would need to be copied every time before making a call the next place so it can reset it for the next digit, otherwise once all places are filled the first time the array would be all true and no other combinations could be calculated.

But, there is a better way. Use bits of an int as the array. X & 1 for the first, X & 2 , X & 4 , X & 8 , etc. This sequence can be represented as (1<<X) or take the first bit and shift it over X times.

& is used to test bits, | is used to set them. In each loop we test if the bit was used (1<<i)&used and skip if it was. At the next place we shift the digits for each digit prefix*10+i and set that digit as used used|(1<<i)

Explanation of looping in the EDIT

The loop calculates Y & (Y-1) which zeroes the lowest set bit. By taking the original and subtracting the result the difference is the lowest bit. This will loop only as many times as there are bits: 3,265,920 times instead of 900,000,000 times. Switching from used to unused is just the ~ operator, and since setting is more efficient than unsetting, it made sense to flip

Going from power of two to its log2 was taken from: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog . This site also details the loop mechanism: https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

Moving original to the bottom:

This is too long for a comment, but This answer can be make somewhat faster by removing the zero handling from the function: ( See edit for fastest answer )

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

Answer 14

A bit late to the party, but very fast (30 ms here) …

 #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 15

iterative version that uses bits extensively

note that array can be changed to any type, and set in any order this will "count"the digits in given order

For more explaination look at my first answer (which is less flexible but much faster) https://stackoverflow.com/a/31928246/2963099

In order to make it iterative, arrays were needed to keep state at each level

This also went though quite a bit of optimization for places the optimizer couldn't figure out

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

Some timings using just 1 to 9 with 1000 reps:

• 15.00s Recursive (modified to count 1 to 9) from https://stackoverflow.com/a/31828305/2963099
• 3.53s swap recursion from https://stackoverflow.com/a/31830671/2963099
• 2.74s nextPermutation version ( https://stackoverflow.com/a/31885811/2963099 )
• 2.34s This Solution
• 1.66s unrolled recursive version in EDIT from https://stackoverflow.com/a/31928246/2963099