我正在尝试获取全部具有唯一数字的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);
}
}
}
那只是将第一个数字与其余数字进行比较。我将不得不做更多的工作来比较其他数字。有一个更好的方法吗？
最佳答案
这是涉及combinatorics的问题的非常典型的示例。
恰好有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数组初始化为迄今未使用的9个数字的集合。 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，则seed将n设置为余数(模数)。因此，是介于0和i(含)之间的整数n-1，0 ≤ i < n。为了删除我们用来决定的
seed部分，我们进行除法:seed = seed / n;。接下来，我们将数字添加到结果中。因为结果是整数，所以我们可以添加一个新的十进制数字位置(通过将结果乘以十)，然后使用
result = result * 10 + digit[i]将数字添加到最低有效位(作为新的最右边的数字)。在C语言中，数字常量末尾的U只是告诉编译器该常量是无符号的(整数)。 (其他的是L的long，UL的unsigned long，如果编译器支持它们，则LL的long long和ULL的unsigned long long。)如果我们要构造一个字符串，则只需将
digit[i]放入char数组中的下一个位置，然后递增该位置。 (要使其成为字符串，只需记住在字符串的末尾放置一个空字符'\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是标识组合的数字，并且它将用最多26个字符串或str字符(以较小者为准)填充len-1，其中每个小写字母字母最多出现一次。如果您觉得这种方法不清楚，请询问:我非常想尝试澄清一下。
您会发现，使用效率低下的算法会浪费大量资源(不仅是电力，还会浪费用户的时间)，这是因为编写慢速，效率低下的代码更容易，而不是真正有效地解决手头的问题。 。我们那样浪费金钱和时间。当正确的解决方案像这种情况下一样简单时(就像我说的那样，这会扩展到很多组合问题)，我宁愿看到程序员花十五分钟来学习并应用它只要有用，就不要看到浪费在蔓延和扩大。
许多答案和评论都围绕生成所有这些组合(并对它们进行计数)。我个人认为它并没有太多用处，因为该集合已经众所周知。实际上，您通常想生成例如小子集-对，三胞胎或更大的集-或满足某些条件的子集集;例如，您可能希望生成十对这样的数字，每个九位数字使用两次，但不能成对使用。我的种子方法可以轻松做到这一点；而不是十进制表示形式，而是使用连续的种子值(0到362879，包括0和362879)。
也就是说，在C中生成(并打印)给定字符串的所有permutations很简单:
#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) 。通常，a(n)≤(1-e)n !，即a(n)<1.7183n !，因此 call 数为O(N!)，是相对于排列的项目数的因数。与调用相比，循环体的迭代时间少了一次，此处为623529次。
使用与第一个代码段相同的数组方法，逻辑很简单，只是这次实际上是使用数组的“修剪掉”部分来存储排列后的字符串。换句话说，我们将剩下的每个字符与要修剪掉的下一个字符(或前置到最后一个字符串)交换，进行递归调用，并还原两个字符。因为在每次递归调用之后都撤消了每个修改，所以缓冲区中的字符串在调用之后与以前相同。就像它从未被修改过一样。
上面的实现确实假定了一个字节的字符(并且不能正确处理例如多字节UTF-8序列)。如果要使用Unicode字符或其他一些多字节字符集中的字符，则应改用宽字符。除了类型更改和更改函数以打印字符串外，不需要其他更改。
关于c - 尝试生成每个唯一数字为9的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31826746/