试图生成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\n", 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?
推荐答案
这是一个问题，涉及到pretty典型的组合数学。
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.
所以，你可以很容易地编写一个函数，这需要在种子的，0≤种子的＆LT; 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;
}
的位阵列初始化为组九个迄今未使用的数字。 I 表示索引到数组，所以位数[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
有关结果的奇次是因为在位数字阵列开关的地方。
The odd order for the results is because the digits in the digit array switch places.
编辑20150826：如果你想在首页组合第（比如说，在字典序），你可以用下面的办法：
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] = '\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;
}
如果您指定数字按升序排列，而 0℃=指数 - LT;长度！，那么缓存将是具有首页个最小值置换。例如，如果位=1234和长度= 4 ，那么指数= 0 将产生缓冲=1234，指数= 1 将产生缓冲=1243，依此类推，直到指数= 23 将产生缓冲=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 [长度] 数组，从右到左类似于 unique9（）进一步以上;然后，性能应该是类似 unique9（）进一步上面，除了 memmove与（） s这个需要（而不是掉期）。
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.
上面，我们有 N 离开位数[] 阵列中未使用的数字，我们可以使用种子来选择下一个未使用的数字。
Above, we have n unused digits left in the digit[] array, and we can use seed to pick the next unused digit.
I =种子％N; 套 I 来的余数（系数的）如果种子是由被分成n个。因此，介于0和 N-1 包容， 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.
要删除种子我们用来决定这部分，我们做了划分：种子=种子/ N; 。
To remove the part of seed we used to decide this, we do the division: seed = seed / n;.
接下来，我们把数字加到我们的结果。因为结果是一个整数，我们只需要添加一个新的十进制数字位置（由十结果乘以），并添加数字到最低显著的地方（如新的最右边的数字），使用结果=结果* 10 +位[I] 。在C中， U 在数字常量的刚刚结束告诉编译器常量是无符号（整数）。 （其他是→为长， UL 为无符号长，如果编译器支持他们， LL >长长和 ULL 为无符号长长）
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.)
如果我们构建一个字符串，我们刚刚把位数[I] 来的char数组中的下一个位置，并增加了位置。 （要使它成为一个字符串，只记得把一个结束串空字符，'\\ 0'，在最后。）
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, '\0', at the very end.)
接下来，因为数字是独一无二的，我们必须删除位数[I] 从位数[] 阵列。我通过更换阵列中位数[I] 由最后一位做到这一点，位数[N-1] ，和递减的离开了数组中的位数， N - ，基本上是修去从它最后一位。所有这一切是通过使用数字做[i] =位数[ - 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).
例如，建立基于每个字母最多一次使用任何ASCII 26个小写字母的单词，我们可以使用
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] = '\0';
return str;
}
通话与 STR 功能指向至少 LEN 字符的字符数组与种子是标识组合，它会填满 STR 高达26或
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.
您看，资源的数量惊人（不仅仅是电力，也是人类用户时间）通过使用低效率的算法输了，只是因为它的更容易的书写速度慢，效率低code的，而不是实际解决手边的问题以有效的方式。我们浪费金钱和时间的方式。当的正确的解决方案是在这种情况下简单 - 就像我说的，这延伸到大集的组合问题，是 - ，我宁愿看到程序员采取刻钟学习它，运用它时是有用的，而不是看到垃圾传播和扩大在
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.
很多答案和注释围绕生成所有这些组合（和计数它们）。我个人不认为在多大用处，因为该集也已经知道。在实践中，您通常要产生如小亚 - 对，三胞胎，或更大的集合 - 或设置符合某些标准的子集;例如，您可能希望产生10对这样的数字，与使用两次，每次九位数字，而不是在一个单一的对。我的种子的方法允许容易;而不是小数重presentation，你连续的种子值，而不是（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\n", result);
fflush(stderr);
return EXIT_SUCCESS;
}
的置换函数是递归的，但它的最大递归深度是字符串长度。呼叫的功能的总数为一的（ N 的），其中的 N 的是串的长度，及一（ N 的）=的 N 的⋅的在的（ N 的-1）+1（序列的 A002627 ），623530电话在这种特殊情况下。一般情况下，的在的（ N 的）≤（1 电子的）的 N 的!,即在（ N ）LT; 1.7183 名词的！所以通话的次数是的 0 的（ N 的！ ），阶乘相对于置换项目数。循环体迭代减少一次相比，电话，这里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.
的逻辑是非常简单的，使用相同的阵列的方法与在第一code片段，所不同的是这个时间的阵列的修整掉的部分实际上用于存储置换后的字符串。换句话说，我们交换仍然留下了下一个字符的每个字符要trimemd关闭（或ppended到最终字符串$ P $），执行递归调用，并恢复两个字符。因为每个修改每次递归调用后撤销，在缓冲区中的字符串是因为它以前呼叫后相同。就好像这是从来没有在第一时间修改。
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序列正常工作）。如果统一code字符，或者以其他多字节字符集，都被使用，那么宽字符应改为使用。除了类型的变化，改变了功能打印字符串，不需要其他更改。
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屋！
