试图用每个唯一的数字生成 9 位数字 [英] Trying to generate 9 digit numbers with each unique digits

问题描述

我正在尝试获取所有具有唯一数字的 9 位数字.我的第一种方法似乎有点过于复杂，编写起来会很乏味.

I am trying obtain 9 digit numbers that all have unique digits. My first approach seems a bit too complex and would be tedious to write.

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

这只是将第一个数字与其余数字进行比较.我将不得不做更多的事情来比较其他数字.有没有更好的方法来做到这一点?

That is just comparing the first number to the rest. I would have to do that many more to compare the other numbers. Is there a better way to do this?

推荐答案

这是一个非常典型的问题示例，涉及组合学.

This is a pretty typical example of a problem involving combinatorics.

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

There are exactly 9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1 = 9! = 362880 nine-digit decimal numbers, where each digit occurs exactly once, and zero is not used at all. This is because there are nine possibilities for the first digit, eight for the second, and so on, since each digit is used exactly once.

因此，您可以轻松编写一个函数，该函数接收 seed, 0 ≤ seed 362880，它返回唯一的组合之一，这样每个组合正好对应一个种子.例如，

So, you can easily write a function, that takes in the seed, 0 ≤ seed < 362880, that returns one of the unique combinations, such that each combination corresponds to exactly one seed. For example,

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的大小减一.

The digit array is initialized to the set of nine thus far unused digits. i indicates the index to that array, so that digit[i] is the actual digit used. Since the digit is used, it is replaced by the last digit in the array, and the size of the array n is reduced by one.

一些示例结果:

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

结果的奇数顺序是因为digit数组中的数字交换了位置.

The odd order for the results is because the digits in the digit array switch places.

Edited 20150826:如果你想要 indexth 组合(比如，按字典顺序)，你可以使用以下方法:

Edited 20150826: If you want the indexth combination (say, in lexicographic order), you can use the following approach:

#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] = '';

    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 将是具有 indexth 最小值的排列.例如，如果 digits="1234" 和 length=4，则 index=0 将产生 buffer="1234"，index=1 将产生 buffer="1243"，依此类推，直到 index=23 将产生 buffer="4321".

If you specify digits in increasing order, and 0 <= index < length!, then buffer will be the permutation having indexth smallest value. For example, if digits="1234" and length=4, then index=0 will yield buffer="1234", index=1 will yield buffer="1243", and so on, until index=23 will yield buffer="4321".

上面的实现绝对没有以任何方式优化.初始循环是计算阶乘，带有溢出检测.避免这种情况的一种方法是使用临时 size_t [length] 数组，并从右到左填充它，类似于上面的 unique9() ；那么，性能应该类似于上面的unique9()，除了memmove()s this需要(而不是swaps).

The above implementation is definitely not optimized in any way. The initial loop is to calculate the factorial, with overflow detection. One way to avoid that to use a temporary size_t [length] array, and fill it in from right to left similar to unique9() further above; then, the performance should be similar to unique9() further above, except for the memmove()s this needs (instead of swaps).

这种方法是通用的.例如，如果您想创建 N 个字符的单词，其中每个字符都是唯一的，和/或仅使用特定字符，则相同的方法将产生一个有效的解决方案.

This approach is generic. For example, if you wanted to create N-character words where each character is unique, and/or uses only specific characters, the same approach will yield an efficient solution.

首先，将任务拆分为多个步骤.

First, split the task into steps.

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

Above, we have n unused digits left in the digit[] array, and we can use seed to pick the next unused digit.

i = seed % n; 将 i 设置为余数(modulus)，如果 seed除以 n.因此，是一个介于 0 和 n-1 之间的整数 i，0 ≤ i .

i = seed % n; sets i to the remainder (modulus) if seed were to be divided by n. Thus, is an integer i between 0 and n-1 inclusive, 0 ≤ i < n.

为了删除我们用来决定这个的seed部分，我们进行了除法:seed = seed/n;.

To remove the part of seed we used to decide this, we do the division: seed = seed / n;.

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

Next, we add the digit to our result. Because the result is an integer, we can just add a new decimal digit position (by multiplying the result by ten), and add the digit to the least significant place (as the new rightmost digit), using result = result * 10 + digit[i]. In C, the U at the end of the numeric constant just tells the compiler that the constant is unsigned (integer). (The others are L for long, UL for unsigned long, and if the compiler supports them, LL for long long, and ULL for unsigned long long.)

如果我们正在构造一个字符串，我们只需将 digit[i] 放在 char 数组中的下一个位置，并增加该位置.(要使其成为字符串，请记住在字符串末尾添加一个字符串结尾的 nul 字符 ''.)

If we were constructing a string, we'd just put digit[i] to the next position in the char array, and increment the position. (To make it into a string, just remember to put an end-of-string nul character, '', at the very end.)

接下来，由于数字是唯一的，我们必须从 digit[] 数组中删除 digit[i].为此，我将 digit[i] 替换为数组中的最后一位数字 digit[n-1]，并减少数组中剩余的位数，n--，本质上是剪掉它的最后一位数字.所有这些都是通过使用 digit[i] = digit[--n]; 来完成的，它完全等同于

Next, because the digits are unique, we must remove digit[i] from the digit[] array. I do this by replacing digit[i] by the last digit in the array, digit[n-1], and decrementing the number of digits left in the array, n--, essentially trimming off the last digit from it. All this is done by using digit[i] = digit[--n]; which is exactly equivalent to

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

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

At this point, if n is still greater than zero, we can add another digit, simply by repeating the procedure.

如果我们不想使用所有数字，我们可以使用单独的计数器(或将 n 与 n -digits_to_use 进行比较).

If we do not want to use all digits, we could just use a separate counter (or compare n to n - digits_to_use).

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

For example, to construct a word using any of the 26 ASCII lowercase letters using each letter at most once, we could use

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] = '';

    return str;
}

调用函数，str 指向一个至少包含 len 个字符的字符数组，seed 是标识组合的数字，它将用最多 26 个或 len-1 个字符(以较小者为准)的字符串填充 str，其中每个小写字母最多出现一次.

Call the function with str pointing to a character array of at least len characters, with seed being the number that identifies the combination, and it'll fill str with a string of up to 26 or len-1 characters (whichever is less) where each lowercase letter occurs at most once.

如果您觉得该方法不清楚，请提问:我非常想尝试澄清.

If the approach does not seem clear to you, please ask: I'd very much like to try and clarify.

您会发现，使用低效算法会损失大量资源(不仅是电力，还有人类用户时间)，因为编写缓慢、低效的代码比更容易，而不是实际以有效的方式解决手头的问题.我们就这样浪费金钱和时间.当正确解决方案像本例一样简单时——就像我说的，这会扩展到大量组合问题——我宁愿让程序员花 15 分钟学习它，并在有用的时候应用它，而不是看到浪费的传播和扩展.

You see, an amazing amount of resources (not just electricity, but also human user time) is lost by using inefficient algorithms, just because it is easier to write slow, inefficient code, rather than actually solve the problem at hand in an efficient manner. We waste money and time that way. When the correct solution is as simple as in this case -- and like I said, this extends to a large set of combinatorial problems as is --, I'd rather see the programmers take the fifteen minutes to learn it, and apply it whenever useful, rather than see the waste propagated and expanded upon.

许多答案和评论都围绕着生成所有这些组合(并计算它们).我个人认为这没有多大用处，因为该系列已经广为人知.在实践中，您通常希望生成例如小子集——成对、三元组或更大的集——或满足某些标准的子集集；例如，您可能希望生成十对这样的数字，每个九位数字使用两次，但不是一对.我的种子方法很容易做到这一点；代替十进制表示，您可以使用连续的种子值(0 到 362879，含).

Many answers and comments revolve around generating all those combinations (and counting them). I personally don't see much use in that, because the set is well known already. In practice, you typically want to generate e.g. small subsets -- pairs, triplets, or larger sets -- or sets of subsets that fulfill some criteria; for example, you might wish to generate ten pairs of such numbers, with each nine-digit number used twice, but not in a single pair. My seed approach allows that easily; instead of decimal representation, you work with the consecutive seed values instead (0 to 362879, inclusive).

也就是说，生成(和打印)给定字符串的所有排列很简单在 C:

That said, it is straightforward to generate (and print) all permutations of a given string in 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
", 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.7183n!，所以调用次数是O(N!)，关于排列的项目数的阶乘.与调用相比，循环体的迭代次数少了 1 次，这里是 623529 次.

The permutation function is recursive, but its maximum recursion depth is the string length. The total number of calls to the function is a(N), where N is the length of the string, and a(n)=n⋅a(n-1)+1 (sequence A002627), 623530 calls in this particular case. In general, a(n)≤(1-e)n!, i.e. a(n)<1.7183n!, so the number of calls is O(N!), factorial with respect to number of items permuted. The loop body is iterated one less time compared to the calls, 623529 times here.

逻辑相当简单，使用与第一个代码片段相同的数组方法，只是这次数组的修剪掉"部分实际上用于存储排列后的字符串.换句话说，我们将剩下的每个字符与下一个要修剪掉的字符(或添加到最后一个字符串)交换，进行递归调用，并恢复这两个字符.因为每次递归调用后都会撤消每次修改，所以缓冲区中的字符串在调用后与之前相同.就好像它从来没有被修改过一样.

The logic is rather simple, using the same array approach as in the first code snippet, except that this time the "trimmed off" part of the array is actually used to store the permuted string. In other words, we swap each character still left with the next character to be trimemd off (or prepended to the final string), do the recursive call, and restore the two characters. Because each modification is undone after each recursive call, the string in the buffer is the same after the call as it was before. Just as if it was never modified in the first place.

上述实现确实假设了一个字节的字符(并且不能正确地使用例如多字节 UTF-8 序列).如果要使用 Unicode 字符或其他多字节字符集中的字符，则应改用宽字符.除了类型改变，以及改变打印字符串的功能，不需要其他改变.

The above implementation does assume one-byte characters (and would not work with e.g. multibyte UTF-8 sequences correctly). If Unicode characters, or characters in some other multibyte character set, are to be used, then wide characters should be used instead. Other than the type change, and changing the function to print the string, no other changes are needed.

这篇关于试图用每个唯一的数字生成 9 位数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！