生成唯一值
我想创建一个C程序来生成0到999999之间的数字，请记住生成的数字不应该包含任何重复的数字。 例如， "123"是可接受的值，但不是"121"因为重复'1' 。 我已经找到了其他程序代码来检查整数是否有重复的数字：
检查整数是否有重复数字。 没有字符串方法或数组
检查数字重复数字的最快方法是什么？
然而，如果我要对1,000,000个不同的值进行检查，这些并不能真正解决我的问题并且它们是非常低效的解决方案。 此外，提供的解决方案是int而不是char[]和char * ，我在我的程序中使用它。 以下是我的代码。 正如您所看到的，我处理高达"012"值没有问题，但是3位及以上值的可能性太多而无法列出，而且编码效率太低。 会感激一些帮助。
int i, j; char genNext[7] = "0"; printf("%s\n", genNext); // loop through to return next pass in sequence while (1) { for (i = 0; i < sizeof(genNext) / sizeof(char); i++) { if (genNext[i] == '9') { char * thisPass = strndup(genNext, sizeof(genNext)); int countDigit = (int) strlen(thisPass); switch (countDigit) { case 1: genNext = "01"; break; case 2: if (strcmp(genNext, "98")) { if (i == 0) { genNext[1] += 1; } else { genNext[0] += 1; genNext[1] == '0'; } } else { genNext = "012"; } break; case 3: if (strcmp(genNext, "987")) { // code to handle all cases } else { genNext = "0123"; } break; case 4: case 5: case 6: // insert code here } break; } else if (genNext[i] == '\0') { break; } else if (genNext[i+1] == '\0') { genNext[i] += 1; for (j = 0; j < i; j++) { if (genNext[i] == genNext[j]) { genNext[i] += 1; } } } else { continue; } } printf("%s\n", genNext); if (strcmp(genNext, "987654") == 0) { break; } }
我面临的主要问题是'9'是正在测试的值的一部分的情况。 例如，基于非重复性的规则以及结果的顺序返回， "897"之后的序列中的下一个值是"901"并且在"067895"是"067912" 。
期望的输出如下：
0 1 2 3 ... 8 9 01 02 03 ... 09 10 12 13 ... 97 98 012 013 014 ... 098 102 103 ... 985 986 987 0123 0124 ... etc etc.
任何帮助都表示赞赏，如果我的问题的任何部分不清楚，请随时澄清。 谢谢！
编辑： 如何生成数字列表的所有排列？ 并没有解决我的问题，因为从"120398"到"120435"的增量作为序列中的下一个“合法”值。
编辑2：更新了问题以包括所需的输出
下面有三种变体算法。 根据您的要求调整变体3。
变体1
这是一种方法。 它实现了一个将10位数的表初始化为0的次要变量; 扫描数字，增加遇到的每个数字的计数，然后检查任何数字计数是否超过我在评论中建议的算法。 一旦发现重复的数字，测试函数就会返回。
#include #include enum { MAX_ITERATION = 1000000 }; static bool duplicate_digits_1(int value) { char buffer[12]; snprintf(buffer, sizeof(buffer), "%d", value); char digits[10] = { 0 }; char *ptr = buffer; char c; while ((c = *ptr++) != '\0') { if (++digits[c - '0'] > 1) return true; } return false; } int main(void) { int count = 0; for (int i = 0; i < MAX_ITERATION; i++) { if (!duplicate_digits_1(i)) { count += printf(" %d", i); if (count > 72) { putchar('\n'); count = 0; } } } putchar('\n'); return 0; }
运行时，它会生成介于0和1,000,000之间的168,571个值，从：
0 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 84 85 86 87 89 90 91 92 93 94 95 96 97 98 102 103 104 105 106 107 108 109 120 123 124 125 126 127 128 129 130 132 134 135 136 137 138 139 140 142 143 145 146 147 148 149 150 152 153 154 156 157 158 159 160 162 163 164 165 167 168 169 170 172 173 174 175 176 178 179 180 182 183 184 185 186 187 189 190 192 193 194 195 196 197 198 201 203 204 205 206 207 208 209 210 213 214 215 216 217 218 219 230 231 234 235 236 237 238 239 240 241 243 245 246 247 248 249 250 251 253 254 256 257 258 259 260 261 263 264 265 267 268 269 270 271 273 … 987340 987341 987342 987345 987346 987350 987351 987352 987354 987356 987360 987361 987362 987364 987365 987401 987402 987403 987405 987406 987410 987412 987413 987415 987416 987420 987421 987423 987425 987426 987430 987431 987432 987435 987436 987450 987451 987452 987453 987456 987460 987461 987462 987463 987465 987501 987502 987503 987504 987506 987510 987512 987513 987514 987516 987520 987521 987523 987524 987526 987530 987531 987532 987534 987536 987540 987541 987542 987543 987546 987560 987561 987562 987563 987564 987601 987602 987603 987604 987605 987610 987612 987613 987614 987615 987620 987621 987623 987624 987625 987630 987631 987632 987634 987635 987640 987641 987642 987643 987645 987650 987651 987652 987653 987654
在您决定“效率不高”之前，请先测量一下。 你是否真的经常锻炼它以至于表现是一个真正的问题？
变式2
创建我在评论中建议的替代版本： 迭代地使用strchr（），检查尾部是否出现第一个数字，如果不是第二个数字是否出现在尾部，依此类推很容易实现给定框架第一个答案：
static bool duplicate_digits_2(int value) { char buffer[12]; snprintf(buffer, sizeof(buffer), "%d", value); char *ptr = buffer; char c; while ((c = *ptr++) != '\0') { if (strchr(ptr, c) != NULL) return true; } return false; }
比较时间后，我得到了这些结果（ ng41使用duplicate_digits_1() ， ng43使用duplicate_digits_2() 。
$ time ng41 > /dev/null real 0m0.175s user 0m0.169s sys 0m0.002s $ time ng43 > /dev/null real 0m0.201s user 0m0.193s sys 0m0.003s $
重复的时间通常显示出类似的结果，但有时我得到的运行速度比ng41快 – 只有一组一百万个数字的时间不明确（所以YMMV – 你的里程可能会有所不同！）。
变式3
您也可以使用此技术，类似于“计数数字”，但不首先转换为字符串（因此它应该更快）。
#include #include #include enum { MAX_ITERATION = 1000000 }; static bool duplicate_digits_3(int value) { char digits[10] = { 0 }; while (value > 0) { if (++digits[value % 10] > 1) return true; value /= 10; } return false; } int main(void) { int count = 0; const char *pad = ""; for (int i = 0; i < MAX_ITERATION; i++) { if (!duplicate_digits_3(i)) { count += printf("%s%d", pad, i); pad = " "; if (count > 72) { putchar('\n'); count = 0; pad = ""; } } } putchar('\n'); return 0; }
因为它避免了对字符串的转换，所以速度要快得多。 我从一系列3次运行中获得的最慢时间是：
real 0m0.063s user 0m0.060s sys 0m0.001s
这大约是其他两个中的任何一个的三倍。
额外时间
我还将MAX_ITERATION的值更改为10,000,000并运行计时。 当然，还有更多被拒绝的产出。
$ time ng41 >/dev/null real 0m1.721s user 0m1.707s sys 0m0.006s $ time ng43 >/dev/null real 0m1.958s user 0m1.942s sys 0m0.008s $ time ng47 >/dev/null real 0m0.463s user 0m0.454s sys 0m0.004s $ ng41 | wc 69237 712891 5495951 $ ng43 | wc 69237 712891 5495951 $ ng47 | wc 69237 712891 5495951 $ cmp <(ng41) <(ng43) $ cmp <(ng41) <(ng47) $ cmp <(ng43) <(ng47) $
这些时间更加稳定; 变体1（ ng41 ）总是比变体2（ ng43 ）更快，但变体3（ ng47 ）两者都有明显的优势。
JFTR：测试是在macOS Sierra 10.12.1上使用GCC 6.2.0在旧的17“MacBook Pro - 2011年初，2.3GHz Intel Core i7和16 GB 1333 MHz DDR3 RAM上进行的 - 不是内存是这个代码的问题。如果您想知道，程序编号是连续的2位数素数。
也是领先的零
此代码生成您想要的数字序列（尽管它只配置为运行高达100,000 - 1,000,000的更改是微不足道的）。 以受虐狂的方式很有趣。
#include #include #include #include enum { MAX_ITERATIONS = 100000 }; /* lz = 1 or 0 - consider that the number has a leading zero or not */ static bool has_duplicate_digits(int value, int lz) { assert(value >= 0 && value < MAX_ITERATIONS + 1); assert(lz == 0 || lz == 1); char digits[10] = { [0] = lz }; while (value > 0) { if (++digits[value % 10] > 1) return true; value /= 10; } return false; } int main(void) { int lz = 0; int p10 = 1; int log_p10 = 0; /* log10(0) is -infinity - but 0 works better */ int linelen = 0; const char *pad = ""; /* The + 1 allows the cycle to reset for the leading zero pass */ for (int i = 0; i < MAX_ITERATIONS + 1; i++) { if (i >= 10 * p10 && lz == 0) { /* Passed through range p10 .. (10*p10-1) once without leading zeros */ /* Repeat, adding leading zeros this time */ lz = 1; i = p10; } else if (i >= 10 * p10) { /* Passed through range p10 .. (10*p10-1) without and with leading zeros */ /* Continue through next range, without leading zeros to start with */ p10 *= 10; log_p10++; lz = 0; } if (!has_duplicate_digits(i, lz)) { /* Adds a leading zero if lz == 1; otherwise, it doesn't */ linelen += printf("%s%.*d", pad, log_p10 + lz + 1, i); pad = " "; if (linelen > 72) { putchar('\n'); pad = ""; linelen = 0; } } } putchar('\n'); return 0; }
样本输出（至100,000）：
0 1 2 3 4 5 6 7 8 9 01 02 03 04 05 06 07 08 09 10 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 84 85 86 87 89 90 91 92 93 94 95 96 97 98 012 013 014 015 016 017 018 019 021 023 024 025 026 027 028 029 031 032 034 035 036 037 038 039 041 042 043 045 046 047 048 049 051 052 053 054 056 057 058 059 061 062 063 064 065 067 068 069 071 072 073 074 075 076 078 079 081 082 083 084 085 086 087 089 091 092 093 094 095 096 097 098 102 103 104 105 106 107 108 109 120 123 124 125 126 127 128 129 130 132 134 135 136 137 138 139 140 … 901 902 903 904 905 906 907 908 910 912 913 914 915 916 917 918 920 921 923 924 925 926 927 928 930 931 932 934 935 936 937 938 940 941 942 943 945 946 947 948 950 951 952 953 954 956 957 958 960 961 962 963 964 965 967 968 970 971 972 973 974 975 976 978 980 981 982 983 984 985 986 987 0123 0124 0125 0126 0127 0128 0129 0132 0134 0135 0136 0137 0138 0139 0142 0143 0145 0146 0147 0148 0149 0152 0153 0154 0156 0157 0158 0159 0162 0163 0164 0165 0167 … 0917 0918 0921 0923 0924 0925 0926 0927 0928 0931 0932 0934 0935 0936 0937 0938 0941 0942 0943 0945 0946 0947 0948 0951 0952 0953 0954 0956 0957 0958 0961 0962 0963 0964 0965 0967 0968 0971 0972 0973 0974 0975 0976 0978 0981 0982 0983 0984 0985 0986 0987 1023 1024 1025 1026 1027 1028 1029 1032 1034 1035 1036 1037 1038 1039 1042 1043 1045 1046 1047 1048 1049 1052 1053 1054 1056 1057 1058 1059 1062 1063 1064 1065 1067 1068 1069 1072 1073 1074 1075 … 9820 9821 9823 9824 9825 9826 9827 9830 9831 9832 9834 9835 9836 9837 9840 9841 9842 9843 9845 9846 9847 9850 9851 9852 9853 9854 9856 9857 9860 9861 9862 9863 9864 9865 9867 9870 9871 9872 9873 9874 9875 9876 01234 01235 01236 01237 01238 01239 01243 01245 01246 01247 01248 01249 01253 01254 01256 01257 01258 01259 01263 01264 01265 01267 01268 01269 01273 01274 01275 01276 01278 01279 01283 01284 01285 01286 01287 01289 01293 01294 01295 01296 01297 01298 … 09827 09831 09832 09834 09835 09836 09837 09841 09842 09843 09845 09846 09847 09851 09852 09853 09854 09856 09857 09861 09862 09863 09864 09865 09867 09871 09872 09873 09874 09875 09876 10234 10235 10236 10237 10238 10239 10243 10245 10246 10247 10248 10249 10253 10254 10256 10257 10258 10259 10263 10264 10265 … 98705 98706 98710 98712 98713 98714 98715 98716 98720 98721 98723 98724 98725 98726 98730 98731 98732 98734 98735 98736 98740 98741 98742 98743 98745 98746 98750 98751 98752 98753 98754 98756 98760 98761 98762 98763 98764 98765 012345 012346 012347 012348 012349 012354 012356 012357 012358 012359 012364 012365 012367 012368 012369 012374 012375 012376 012378 012379 012384 012385 012386 … 098653 098654 098657 098671 098672 098673 098674 098675 098712 098713 098714 098715 098716 098721 098723 098724 098725 098726 098731 098732 098734 098735 098736 098741 098742 098743 098745 098746 098751 098752 098753 098754 098756 098761 098762 098763 098764 098765
使用循环（从0到999,999，包括0和999,999），并拒绝重复数字的值听起来像是对我来说最直接的实现。
reject-if-duplicate-digits函数可以非常快。 例如，考虑一下
int has_duplicate_digits(unsigned int value) { unsigned int digit_mask = 0U; do { /* (value % 10U) is the value of the rightmost decimal digit of (value). 1U << (value % 10U) refers to the value of the corresponding bit -- bit 0 to bit 9. */ const unsigned int mask = 1U << (value % 10U); /* If the bit is already set in digit_mask, we have a duplicate digit in value. */ if (mask & digit_mask) return 1; /* Mark this digit as seen in the digit_mask. */ digit_mask |= mask; /* Drop the rightmost digit off value. Note that this is integer division. */ value /= 10U; /* If we have additional digits, repeat loop. */ } while (value); /* No duplicate digits found. */ return 0; }
这实际上是一个经典的组合问题。 下面是使用TAOCP 7.2.1.2中的算法L和TAOCP 7.2.1.3中的算法T实现概念的certificate。 可能存在一些错误。 有关详细信息，请参阅算法。
这是一个解释。 设t为位数。 对于t == 10 ，问题是生成所有t！ 以字典顺序排列集合{0,1,2，…，9}（算法L）。
对于t> 0和t <10，这将分解为1）从10个可能的数字生成t个数字的所有组合。 2）。 对于每个组合，生成所有t！ 排列。
最后，你可以排序所有10个！ + 10！ / 2 + 10！ / 3！ + .. + 10个结果。 一开始排序可能看起来很昂贵。 但首先，组合生成已经是词汇顺序。 其次，排列生成也是词汇顺序。 所以序列实际上非常规则。 QSort在这里并不是太糟糕。
#include #include #include #include static inline int compare_str(const void *a, const void *b) { return strcmp(a, b); } static inline int compare_char(const void *a, const void *b) { char ca = *((char *) a); char cb = *((char *) b); if (ca < cb) return -1; if (ca > cb) return 1; return 0; } // Algorithm L in TAOCP 7.2.1.2 static inline char *algorithm_l(int n, const char *c, char *r) { char a[n + 1]; memcpy(a, c, n); a[n] = '\0'; qsort(a, n, 1, compare_char); while (1) { // L1. [Visit] memcpy(r, a, n + 1); r += n + 1; // L2. [Find j] int j = n - 1; while (j > 0 && a[j - 1] >= a[j]) --j; if (j == 0) break; // L3. [Increase a[j - 1]] int l = n; while (l >= 0 && a[j - 1] >= a[l - 1]) --l; char tmp = a[j - 1]; a[j - 1] = a[l - 1]; a[l - 1] = tmp; // L4. [Reverse a[j]...a[n-1]] int k = j + 1; l = n; while (k < l) { char tmp = a[k - 1]; a[k - 1] = a[l - 1]; a[l - 1] = tmp; ++k; --l; } } return r; } // Algorithm T in TAOCP 7.2.1.2 static inline void algorithm_t(int t, char *r) { assert(t > 0); assert(t < 10); // Algorithm T in TAOCP 7.2.1.3 // T1. [Initialize] char c[12]; // the digits for (int i = 0; i < t; ++i) c[i] = '0' + i; c[t] = '9' + 1; c[t + 1] = '0'; char j = t; char x = '0'; while (1) { // T2. [Visit] r = algorithm_l(t, c, r); if (j > 0) { x = '0' + j; } else { // T3. [Easy case?] if (c[0] + 1 < c[1]) { ++c[0]; continue; } j = 2; // T4. [Find j] while (1) { c[j - 2] = '0' + j - 2; x = c[j - 1] + 1; if (x != c[j]) break; ++j; } // T5. [Done?] if (j > t) break; } // T6. [Increase c[j - 1]] c[j - 1] = x; --j; } } static inline void generate(int t) { assert(t >= 0 && t <= 10); if (t == 0) return; int n = 1; int k = 10; for (int i = 1; i <= t; ++i, --k) n *= k; char *r = (char *) malloc((t + 1) * n); if (t == 10) { algorithm_l(10, "0123456789", r); } else { algorithm_t(t, r); } qsort(r, n, t + 1, strcmpv); for (int i = 0; i < n; ++i, r += t + 1) printf("%s\n", r); } int main() { for (int t = 1; t <= 10; ++t) generate(t); }
效率：这是实施效率不高。 它是算法的直接转换，以便于理解。 然而，它仍然比迭代10 ^ 10个数字更有效。 生成从0到9876543210的所有数字大约需要2.5秒。这包括将它们写入文件的时间，94MB输出文件，一行一行。 最多6位数，大约需要0.05秒。
如果您希望这些数字按程序中的顺序排列，则最好生成上述数字以准备表格并稍后使用该表格。 即使是从0到9876543210的表，也只有不到一千万的数字，这在今天的计算机中并不是一个非常大的数字。 在您的情况下，最多六位数，只有不到一百万的数字。