我正在尝试获取所有具有唯一数字的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);
}
}
}
这只是将第一个数字与其余数字进行比较.我不得不做更多的事情来比较其他数字.有一个更好的方法吗？
Nom*_*mal 47
这是涉及组合学的问题的一个非常典型的例子.
恰好有9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1= 9!= 362880个九位十进制数,其中每个数字恰好出现一次,并且根本不使用零.这是因为第一个数字有九种可能性,第二个数字有八种,依此类推,因为每个数字只使用一次.
所以,可以很容易地写出一个功能,即取入种子,0≤ 种子 <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减少一.
一些示例结果:
unique9(0U) == 198765432U
unique9(1U) == 218765439U
unique9(10U) == 291765438U
unique9(1000U) == 287915436U
unique9(362878U) == 897654321U
unique9(362879U) == 987654321U
结果的奇数顺序是因为digit数组开关中的数字位置.
编辑20150826:如果您想要index组合(例如,按字典顺序排列),您可以使用以下方法:
#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最小值的置换.例如,如果digits="1234"和length=4,index=0则会产生buffer="1234",index=1将产生buffer="1243",等等,直到index=23产生buffer="4321".
绝对没有以任何方式优化上述实现.初始循环是通过溢出检测计算阶乘.避免使用临时size_t [length]数组的一种方法,并从右到左填充,类似于unique9()上面的内容; 然后,性能应该类似于unique9()上面的进一步,除了memmove()这需要(而不是交换).
这种方法是通用的.例如,如果要创建每个字符唯一的N字符单词,和/或仅使用特定字符,则相同的方法将产生有效的解决方案.
首先,将任务分成几个步骤.
在上面,我们n在digit[]数组中留下了未使用的数字,我们可以seed用来选择下一个未使用的数字.
i = seed % n;如果被除以,则设置i为余数(模数).因此,为整数0和之间包容.seednin-10 ? i < n
为了删除seed我们用来决定这个的部分,我们进行划分:seed = seed / n;.
接下来,我们将数字添加到结果中.因为结果是整数,我们可以添加一个新的十进制数字位置(通过将结果乘以十),并将数字添加到最不重要的位置(作为新的最右边的数字),使用result = result * 10 + digit[i].在C中,U数字常量的末尾只告诉编译器常量是无符号的(整数).(其他的是Lfor long,ULfor unsigned long,如果编译器支持它们,LLfor long long和ULLfor unsigned long long.)
如果我们构造一个字符串,我们只需要放入digit[i]char数组中的下一个位置,然后递增位置.(要使它成为一个字符串,只需记住在最后放置一个字符串结尾的nul字符'\0'.)
接下来,因为数字是唯一的,我们必须digit[i]从digit[]数组中删除.我这样做是通过替换digit[i]数组中的最后一位数字digit[n-1],并减少数组中剩余的数字位数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指向至少len字符的字符数组来调用函数,使用seed标识组合的数字,并且它将填充str最多26个字符串或len-1字符(以较小者为准),其中每个小写字母最多出现一次.
如果您认为这种方法不明确,请询问:我非常想尝试澄清.
你看,使用效率低下的算法会丢失大量的资源(不仅仅是电力,而且还有人类的用户时间),因为它更容易编写缓慢,低效的代码,而不是以有效的方式实际解决手头的问题.我们这样浪费金钱和时间.当正确的解决方案就像在这种情况下一样简单 - 就像我说的那样,这延伸到了一大堆组合问题 - 我宁愿看到程序员花了十五分钟来学习它并应用它只要有用,而不是看到废物繁殖和扩展.
许多答案和评论围绕生成所有这些组合(并计算它们).我个人认为没有多大用处,因为这套装置已经众所周知.在实践中,您通常希望生成例如小子集 - 对,三元组或更大集 - 或满足某些标准的子集集; 例如,您可能希望生成十对这样的数字,每个九位数使用两次,但不能在一对中使用.我的种子方法很容易实现; 而不是十进制表示,而是使用连续的种子值(0到362879,包括0和362879).
也就是说,在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;
}
置换函数是递归的,但其最大递归深度是字符串长度.对函数的调用总数是a(N),其中N是字符串的长度,并且a(n)= n · a(n -1)+1(序列A002627),在这种特殊情况下调用623530 .通常,a(n)≤(1- e)n !,即a(n)<1.7183 n !,因此调用次数为O(N!),关于项目数量的阶乘.与调用相比,循环体的迭代次数少了623529次.
逻辑相当简单,使用与第一个代码片段相同的数组方法,除了这次数组的"修剪掉"部分实际上用于存储置换字符串.换句话说,我们将剩下的每个字符与下一个字符交换为trimemd(或预先添加到最后的字符串),进行递归调用,并恢复两个字符.因为每次递归调用后每个修改都被撤消,所以缓冲区中的字符串在调用之后与之前相同.就好像它从未被修改过一样.
上面的实现确实假设一个字节的字符(并且不能正确地使用例如多字节UTF-8序列).如果要使用Unicode字符或某些其他多字节字符集中的字符,则应使用宽字符.除了类型更改,并更改函数以打印字符串,不需要进行其他更改.
use*_*109 14
给定一组数字,可以使用相当简单的函数生成这些数字的下一个排列(让我们调用该函数nextPermutation).如果数组以排序顺序的所有数字开头,则该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 };
然后代码将按升序生成并显示这九个数字的所有362880个排列.
该nextPermutation功能有三个步骤
x),后跟一个更大的数字y大于的第一个数字(称之为)x,并交换x和yy现在是在哪里x,并且右边的所有数字y都按降序排列,交换它们以便它们按升序排列让我举一个例子来说明.假设数组按此顺序具有数字
1 9 5 4 8 7 6 3 2
第一步就是找到4.由于8 7 6 3 2是按降序排列,因此4是第一个数字(从数组的末尾开始),后面跟着一个更大的数字.
第二步将找到6,因为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
因此,给定数字的任何排列,函数将通过交换几个数字来找到下一个排列.唯一的例外是最后一个排列,其中所有数字的顺序相反,即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函数将找到2,3,7和9的所有排列.
只是为了完整性,这是arrayToInt函数中使用的main函数.此功能仅用于演示目的.它假定数组只包含单个数字,并且不会检查溢出.它适用于9位数字,前提是a int至少为32位.
int arrayToInt( int array[], int length )
{
int result = 0;
for ( int i = 0; i < length; i++ )
result = result * 10 + array[i];
return result;
}
由于似乎对此算法的性能有一些兴趣,这里有一些数字:
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
测试的CPU是2.5Ghz Intel i5处理器.该算法每秒产生大约2亿个排列,并且花费不到2毫秒来生成9个数字的所有排列.
同样令人感兴趣的是,平均而言,该算法每次排列仅需要大约1.5次交换.有一半的时间,算法只是交换数组中的最后两个数字.在24个案例中的11个案例中,该算法进行了两次交换.因此,在24个案例中只有1个算法需要两次以上的交换.
最后,我尝试使用以下两个数组的算法
int array[] = { 1, 2, 2, 3 }; // generates 12 permutations
int array[] = { 1, 2, 2, 3, 3, 3, 4 }; // generates 420 permutations
排列的数量与预期的一样,输出似乎是正确的,因此如果数字不是唯一的,似乎算法也有效.
Pau*_*kin 12
递归在这里很好用.
#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;
}
这是一个简单的程序,它将打印一组字符的所有排列.您可以轻松转换它以生成所需的所有数字:
#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;
}
它使用递归但不使用位掩码,可用于任何字符集.它还计算排列的数量,因此您可以验证它是否为一组n个字符生成阶乘(n)排列.
这里有很多很长的代码块.最好多思考,少编码.
我们希望在没有浪费精力的情况下完全生成每种可能性.事实证明,这是可能的,每发出一个数字只需要一定量的努力.
没有代码你会怎么做？获取10张卡并在其上写入0到9的数字.在桌面上画一排9个方格.选一张卡片.把它放在第一个方格中,另一个放在第二个方格中等等.当你选择9时,你就得到了你的第一个数字.现在移除最后一张卡并将其替换为每种可能的替代品.(在这种情况下只有1个.)每次填充所有方格时,你都有另一个数字.当您完成最后一个方格的所有替代方法时,请执行最后一个方格2.重复最后一个方格等,直到您考虑了所有方框的所有替代方案.
编写一个简洁的程序来做这个就是选择简单的数据结构.对9行的行使用一个字符数组.
使用另一个阵列作为卡组.要从存储在数组A [0 .. N-1]中的大小N集合中删除元素,我们使用旧技巧.假设您要删除的元素是A [I].将A [I]的值保存到侧面.然后复制最后一个元素A [N-1]"向下",覆盖A [I].新集合为A [0 .. N-2].这很好,因为我们不关心集合中的顺序.
其余的是使用递归思维来枚举所有可能的替代方案.如果我知道如何从大小为M的字符集中找到所有选择到大小为N的字符串,那么要获得算法,只需为第一个字符串位置选择每个可能的字符,然后重复选择N-1的其余部分.其余大小为M-1的字符.我们得到了一个很好的12行功能:
#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;
}
你没有提到是否可以在第一个位置加零.假设不是.由于我们很好地理解了算法,因此很容易避免在第一个位置选择零.只要通过观察!posC中的值为1,如果pos为0和0 ,就可以跳过这种可能性.如果你不喜欢这个略显模糊的习语,那么尝试(pos == 0 ? 1 : 0)作为一个更易读的替代品:
#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;
}
而不是10个变量,我会为10个数字中的每个数字创建一个具有位设置(和可测试)的变量.然后,您只需要对每个数字对应的位进行循环设置(并测试).像这样的东西:
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种组合.
然而 - 有一个评论是关于一个答案最快,这促使后续.有(计算这一个)三个可比较的答案.快速检查:
real 0m0.951s
user 0m0.894s
sys 0m0.056s
real 0m49.108s
user 0m49.041s
sys 0m0.031s
real 1m27.597s
user 1m27.476s
sys 0m0.051s
你可以使用一个掩码来设置标志,标志是否已经在数字中看到了数字.像这样:
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;
}
这是一种方法 - 从一组唯一数字开始,然后随机地将它们随机混乱:
#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
请注意,这些是唯一十进制数字的字符串,而不是数字值; 如果你想要相应的整数值,你需要进行类似的转换
long val = strtol( digits, NULL, 10 );
检查此代码.
#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;
}
如果您有任何疑问,请随时提出.
我推荐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;
}
这种方法对传入的数字是破坏性的,实际上不必是数字,或者对于那个问题是唯一的.
如果您希望以排序递增顺序生成的输出值有更多工作:
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));
}
这应打印出三位十六进制值的有序列表,没有重复的数字:
seed 0 -> 012
seed 1 -> 013
...
seed 3358 -> FEC
seed 3359 -> FED
我不知道你用这些精心设计的数字序列实际上在做什么.如果一些贫困维护工程师将不得不一起走在你身后修复一些bug,我建议有序的版本,因为它是这样一个人来的种子从/到序列值转换更容易.
这是使用嵌套的有点丑陋但非常快速的解决方案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;
}
使用一些宏也是一样的.
#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;
}
我确信有更好的方法来编写这些宏,但这是我能想到的.
编辑: 进一步分析后,更多的递归展开和仅迭代设置位导致显着改善,在我的测试中大约快了五倍.这是用OUTPUT UNSET测试来比较算法速度而不是控制台输出,起点是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].但是,每次在下一个地方打电话之前都需要复制它,这样它就可以将它重置为下一个数字,否则一旦所有位置都被填充,第一次数组将全部为真,并且不能计算其他组合.
但是,有一种更好的方法.使用a的位int作为数组. X & 1用于第一,X & 2,X & 4,X & 8,等.该序列可以表示为(1<<X)或采取所述第一比特和超过X倍移位它.
&用于测试位,|用于设置它们.在每个循环中,我们测试该位是否被使用(1<<i)&used,如果是,则跳过.在下一个地方,我们移动每个数字的数字prefix*10+i并将该数字设置为使用used|(1<<i)
EDIT中循环的说明
循环计算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;
}
一种简单的方法是创建一个包含九个不同值的数组,将其混洗,然后打印混洗数组.根据需要重复多次.例如,使用标准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个唯一的数字.请注意,这不会阻止重复.