c - 尝试生成每个唯一数字为9的数字

Question

我正在尝试获取全部具有唯一数字的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

这是涉及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字符或其他一些多字节字符集中的字符，则应改用宽字符。除了类型更改和更改函数以打印字符串外，不需要其他更改。