C中升序排列的n个数字的不同组合
Different combinations of n numbers in ascending order in C
我想写一个函数，在 C 中按升序显示 n 个数字的所有不同组合。
例如，如果 n=2：
01, 02, 03, ..., 09, 12, ..., 79, 89.
函数命名如下：
void ft_print_combn(int n);
我尝试这样做，但它给我带来了麻烦，我不知道如何更改我的代码以给出正确的顺序：
#include <unistd.h>
#include <stdio.h>
void ft_putchar(char a)
{
write(1, &a, 1);
}
void ft_print_combn(int n)
{
int combn[n];
int p;
int pos;
int position;
if (n <= 0 || n >= 10)
return ;
else
{
p = 0;
pos = 0;
while (p < n)
{
combn[p] = p;
//ft_putchar(combn[p] + '0');
p++;
}
while(n-position-1>=1 && n-(position+1)-1>=0)
{
while(combn[n-pos-1]>combn[n-(pos+1)-1])
{
while(p<=n)
{
//ft_putchar(combn[pos] + '0');
//combn[n-pos-1]=combn[n-(pos+1)-1]+1;
printf("%d[%d] > %d[%d]\n", combn[n-p-1], n-p-1 , combn[n-(p+1)-1], n-(p+1)-1);
combn[n-p-1]=combn[n-(p+1)-1]+1;
p++;
}
pos++;
}
combn[n-pos-1]=combn[n-(pos+1)-1]+1;
position++;
}
}
}
int main()
{
ft_print_combn(4);
}
第一个组合将所有数字设置为其最小值，最左边的数字从 0 开始。对于四位数：
0123
最后一个组合将所有数字设置为其最大值，从 10 - N 开始，N 数字。对于四位数：
6789
中间的组合是通过“递增”前面的组合找到的。这涉及从右到左的搜索，寻找最右边不是最大值的数字。例如，如果 4 位数字的当前组合是：
0589
^ this is the rightmost digit that can be incremented
通过递增该数字并将其右侧的所有数字设置为比前一个数字多一位来形成下一个组合：
0678
^ this is the first changed digit, the digits to the right are set sequentially
这是一个可能的实现，使用了一堆嵌套的 while 和 do while 循环：
#include <unistd.h>
#include <stdio.h>
void ft_putchar(char a)
{
write(1, &a, 1);
}
void ft_print_combn(int n)
{
int combn[n];
int p;
if (n <= 0 || n >= 10)
return ;
else
{
p = 0;
/* Set first combination. */
while (p < n)
{
combn[p] = p;
p++;
}
while (p > 0)
{
int maxdigit = 10;
/* Print current combination. */
for (p = 0; p < n; p++)
{
ft_putchar(combn[p] + '0');
}
/*
* Work out next combination, if any.
*
* Search from right to left looking for a digit that can be
* incremented. E.g. rightmost digit can be incremented if
* less than 9, otherwise the digit to its left can be incremented
* if less than 8, etc.
*/
p = n;
while (p--)
{
int digit = combn[p];
/*
* Maximum digit value decreases during search from
* right to left.
*/
if (digit < --maxdigit)
{
/*
* Found a digit that can be incremented.
*
* Increment that digit and reset all the digits to its
* right to their minimum allowed value.
*/
do
{
combn[p++] = ++digit;
}
while (p < n);
/* Print separator. */
ft_putchar(',');
ft_putchar(' ');
/* Break out of search. */
break;
}
}
}
ft_putchar('\n');
}
}
int main()
{
ft_print_combn(4);
}
输出：
0123, 0124, 0125, 0126, 0127, 0128, 0129, 0134, 0135, 0136, 0137, 0138, 0139, 0145, 0146, 0147, 0148, 0149, 0156, 0157, 0158, 0159, 0167, 0168, 0169, 0178, 0179, 0189, 0234, 0235, 0236, 0237, 0238, 0239, 0245, 0246, 0247, 0248, 0249, 0256, 0257, 0258, 0259, 0267, 0268, 0269, 0278, 0279, 0289, 0345, 0346, 0347, 0348, 0349, 0356, 0357, 0358, 0359, 0367, 0368, 0369, 0378, 0379, 0389, 0456, 0457, 0458, 0459, 0467, 0468, 0469, 0478, 0479, 0489, 0567, 0568, 0569, 0578, 0579, 0589, 0678, 0679, 0689, 0789, 1234, 1235, 1236, 1237, 1238, 1239, 1245, 1246, 1247, 1248, 1249, 1256, 1257, 1258, 1259, 1267, 1268, 1269, 1278, 1279, 1289, 1345, 1346, 1347, 1348, 1349, 1356, 1357, 1358, 1359, 1367, 1368, 1369, 1378, 1379, 1389, 1456, 1457, 1458, 1459, 1467, 1468, 1469, 1478, 1479, 1489, 1567, 1568, 1569, 1578, 1579, 1589, 1678, 1679, 1689, 1789, 2345, 2346, 2347, 2348, 2349, 2356, 2357, 2358, 2359, 2367, 2368, 2369, 2378, 2379, 2389, 2456, 2457, 2458, 2459, 2467, 2468, 2469, 2478, 2479, 2489, 2567, 2568, 2569, 2578, 2579, 2589, 2678, 2679, 2689, 2789, 3456, 3457, 3458, 3459, 3467, 3468, 3469, 3478, 3479, 3489, 3567, 3568, 3569, 3578, 3579, 3589, 3678, 3679, 3689, 3789, 4567, 4568, 4569, 4578, 4579, 4589, 4678, 4679, 4689, 4789, 5678, 5679, 5689, 5789, 6789
使用递归函数更容易实现（如@4386427 所建议）：
#include <stdio.h>
void combn(int start, int n, const char* s)
{
if(n==0){
printf("%s\n", s);
return;
}
for(int i=start;i<=9;i++){
char s2[11];
sprintf(s2, "%s%i",s, i);
combn(i+1,n-1, s2);
}
}
void ft_print_combn(int n)
{
if (n>=1 && n<=10)
combn(0,n,"");
}
int main (int argc, char* args[])
{
ft_print_combn(3);
}
您可以使用该方法打印所有 N 位代码
n 需要 > O
#include <stdio.h>
int int_len(int nb) {
int len = 1;
while (nb > 0){
len++;
nb /= 10;
}
return len - 1;
}
void ft_combi(int n)
{
int combi = n / n; // add error if n = 0
for (int i = 0; i < n; i++)
combi *= 10;
for (int i = 0; i < combi; i++) {
for (int j = 0; j > int_len(i) - n; j--)
printf("0");
if (i == 0)
printf("\n");
else
printf("%d\n", i);
}
}
int main()
{
ft_combi(2);
}
此解决方案将完成这项工作（阅读所附评论以了解其工作原理）：
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
/* Set of available chars in the order they must be considered. */
char alpha[] = "0123456789";
/* hold the pointers to the chars to print a solution */
char *sol[sizeof alpha];
static char *sep = ""; /* initial separator is nothing (no separator) */
void
print_numbers(
int n, /* number of characters to generate per sol. */
char *from, /* where to take the chars from */
int l) /* actual string length */
{
if (n) { /* we need to descend recursively as we have still chars to add */
char *p;
/* from the next available char to the end of the string
* of available chars */
for (p = from+1; *p; p++) {
/* save the pointer to be able to print it */
sol[l] = p;
/* call recursively with updated parameters */
print_numbers(n-1, p, l+1);
}
} else {
/* print the solution (the characters point to in sol array) */
sol[l] = NULL; /* end the array of pointers */
printf("%s", sep); /* print the separator string */
sep = ", "; /* change separator into a comma and a space */
int i;
for (i = 0; sol[i]; i++) /* print the chars pointed to in sol */
putchar(*sol[i]);
}
}
int main(int argc, char **argv)
{
int opt;
int n = 2; /* default print two digits, as stated in SO question */
/* we use getopt(3) to process a possible option -n to specify the
* actual number of characters we want to print. */
while ((opt = getopt(argc, argv, "n:")) != EOF) {
switch (opt) {
/* option -n allows to select any other length */
case 'n': n = atoi(optarg); break;
}
}
/* initially call the recursive function */
print_numbers(n, alpha, 0);
/* print a last \n so we end in a new line */
puts("");
}
如果运行没有参数，它会打印你发布的样本：
$ asc
01, 02, 03, 04, 05, 06, 07, 08, 09, 12, 13, 14, 15, 16, 17, 18, 19, 23, 24, 25, 26, 27, 28, 29, 34, 35, 36, 37, 38, 39, 45, 46, 47, 48, 49, 56, 57, 58, 59, 67, 68, 69, 78, 79, 89
$ _
或者如果您使用 -n :
$ asc -n 3
012, 013, 014, 015, 016, 017, 018, 019, 023, 024, 025, 026, 027, 028, 029, 034, 035, 036, 037, 038, 039, 045, 046, 047, 048, 049, 056, 057, 058, 059, 067, 068, 069, 078, 079, 089, 123, 124, 125, 126, 127, 128, 129, 134, 135, 136, 137, 138, 139, 145, 146, 147, 148, 149, 156, 157, 158, 159, 167, 168, 169, 178, 179, 189, 234, 235, 236, 237, 238, 239, 245, 246, 247, 248, 249, 256, 257, 258, 259, 267, 268, 269, 278, 279, 289, 345, 346, 347, 348, 349, 356, 357, 358, 359, 367, 368, 369, 378, 379, 389, 456, 457, 458, 459, 467, 468, 469, 478, 479, 489, 567, 568, 569, 578, 579, 589, 678, 679, 689, 789
$ _
我想写一个函数，在 C 中按升序显示 n 个数字的所有不同组合。
例如，如果 n=2： 01, 02, 03, ..., 09, 12, ..., 79, 89.
函数命名如下：
void ft_print_combn(int n);
我尝试这样做，但它给我带来了麻烦，我不知道如何更改我的代码以给出正确的顺序：
#include <unistd.h>
#include <stdio.h>
void ft_putchar(char a)
{
write(1, &a, 1);
}
void ft_print_combn(int n)
{
int combn[n];
int p;
int pos;
int position;
if (n <= 0 || n >= 10)
return ;
else
{
p = 0;
pos = 0;
while (p < n)
{
combn[p] = p;
//ft_putchar(combn[p] + '0');
p++;
}
while(n-position-1>=1 && n-(position+1)-1>=0)
{
while(combn[n-pos-1]>combn[n-(pos+1)-1])
{
while(p<=n)
{
//ft_putchar(combn[pos] + '0');
//combn[n-pos-1]=combn[n-(pos+1)-1]+1;
printf("%d[%d] > %d[%d]\n", combn[n-p-1], n-p-1 , combn[n-(p+1)-1], n-(p+1)-1);
combn[n-p-1]=combn[n-(p+1)-1]+1;
p++;
}
pos++;
}
combn[n-pos-1]=combn[n-(pos+1)-1]+1;
position++;
}
}
}
int main()
{
ft_print_combn(4);
}
第一个组合将所有数字设置为其最小值，最左边的数字从 0 开始。对于四位数：
0123
最后一个组合将所有数字设置为其最大值，从 10 - N 开始，N 数字。对于四位数：
6789
中间的组合是通过“递增”前面的组合找到的。这涉及从右到左的搜索，寻找最右边不是最大值的数字。例如，如果 4 位数字的当前组合是：
0589
^ this is the rightmost digit that can be incremented
通过递增该数字并将其右侧的所有数字设置为比前一个数字多一位来形成下一个组合：
0678
^ this is the first changed digit, the digits to the right are set sequentially
这是一个可能的实现，使用了一堆嵌套的 while 和 do while 循环：
#include <unistd.h>
#include <stdio.h>
void ft_putchar(char a)
{
write(1, &a, 1);
}
void ft_print_combn(int n)
{
int combn[n];
int p;
if (n <= 0 || n >= 10)
return ;
else
{
p = 0;
/* Set first combination. */
while (p < n)
{
combn[p] = p;
p++;
}
while (p > 0)
{
int maxdigit = 10;
/* Print current combination. */
for (p = 0; p < n; p++)
{
ft_putchar(combn[p] + '0');
}
/*
* Work out next combination, if any.
*
* Search from right to left looking for a digit that can be
* incremented. E.g. rightmost digit can be incremented if
* less than 9, otherwise the digit to its left can be incremented
* if less than 8, etc.
*/
p = n;
while (p--)
{
int digit = combn[p];
/*
* Maximum digit value decreases during search from
* right to left.
*/
if (digit < --maxdigit)
{
/*
* Found a digit that can be incremented.
*
* Increment that digit and reset all the digits to its
* right to their minimum allowed value.
*/
do
{
combn[p++] = ++digit;
}
while (p < n);
/* Print separator. */
ft_putchar(',');
ft_putchar(' ');
/* Break out of search. */
break;
}
}
}
ft_putchar('\n');
}
}
int main()
{
ft_print_combn(4);
}
输出：
0123, 0124, 0125, 0126, 0127, 0128, 0129, 0134, 0135, 0136, 0137, 0138, 0139, 0145, 0146, 0147, 0148, 0149, 0156, 0157, 0158, 0159, 0167, 0168, 0169, 0178, 0179, 0189, 0234, 0235, 0236, 0237, 0238, 0239, 0245, 0246, 0247, 0248, 0249, 0256, 0257, 0258, 0259, 0267, 0268, 0269, 0278, 0279, 0289, 0345, 0346, 0347, 0348, 0349, 0356, 0357, 0358, 0359, 0367, 0368, 0369, 0378, 0379, 0389, 0456, 0457, 0458, 0459, 0467, 0468, 0469, 0478, 0479, 0489, 0567, 0568, 0569, 0578, 0579, 0589, 0678, 0679, 0689, 0789, 1234, 1235, 1236, 1237, 1238, 1239, 1245, 1246, 1247, 1248, 1249, 1256, 1257, 1258, 1259, 1267, 1268, 1269, 1278, 1279, 1289, 1345, 1346, 1347, 1348, 1349, 1356, 1357, 1358, 1359, 1367, 1368, 1369, 1378, 1379, 1389, 1456, 1457, 1458, 1459, 1467, 1468, 1469, 1478, 1479, 1489, 1567, 1568, 1569, 1578, 1579, 1589, 1678, 1679, 1689, 1789, 2345, 2346, 2347, 2348, 2349, 2356, 2357, 2358, 2359, 2367, 2368, 2369, 2378, 2379, 2389, 2456, 2457, 2458, 2459, 2467, 2468, 2469, 2478, 2479, 2489, 2567, 2568, 2569, 2578, 2579, 2589, 2678, 2679, 2689, 2789, 3456, 3457, 3458, 3459, 3467, 3468, 3469, 3478, 3479, 3489, 3567, 3568, 3569, 3578, 3579, 3589, 3678, 3679, 3689, 3789, 4567, 4568, 4569, 4578, 4579, 4589, 4678, 4679, 4689, 4789, 5678, 5679, 5689, 5789, 6789
使用递归函数更容易实现（如@4386427 所建议）：
#include <stdio.h>
void combn(int start, int n, const char* s)
{
if(n==0){
printf("%s\n", s);
return;
}
for(int i=start;i<=9;i++){
char s2[11];
sprintf(s2, "%s%i",s, i);
combn(i+1,n-1, s2);
}
}
void ft_print_combn(int n)
{
if (n>=1 && n<=10)
combn(0,n,"");
}
int main (int argc, char* args[])
{
ft_print_combn(3);
}
您可以使用该方法打印所有 N 位代码 n 需要 > O
#include <stdio.h>
int int_len(int nb) {
int len = 1;
while (nb > 0){
len++;
nb /= 10;
}
return len - 1;
}
void ft_combi(int n)
{
int combi = n / n; // add error if n = 0
for (int i = 0; i < n; i++)
combi *= 10;
for (int i = 0; i < combi; i++) {
for (int j = 0; j > int_len(i) - n; j--)
printf("0");
if (i == 0)
printf("\n");
else
printf("%d\n", i);
}
}
int main()
{
ft_combi(2);
}
此解决方案将完成这项工作（阅读所附评论以了解其工作原理）：
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
/* Set of available chars in the order they must be considered. */
char alpha[] = "0123456789";
/* hold the pointers to the chars to print a solution */
char *sol[sizeof alpha];
static char *sep = ""; /* initial separator is nothing (no separator) */
void
print_numbers(
int n, /* number of characters to generate per sol. */
char *from, /* where to take the chars from */
int l) /* actual string length */
{
if (n) { /* we need to descend recursively as we have still chars to add */
char *p;
/* from the next available char to the end of the string
* of available chars */
for (p = from+1; *p; p++) {
/* save the pointer to be able to print it */
sol[l] = p;
/* call recursively with updated parameters */
print_numbers(n-1, p, l+1);
}
} else {
/* print the solution (the characters point to in sol array) */
sol[l] = NULL; /* end the array of pointers */
printf("%s", sep); /* print the separator string */
sep = ", "; /* change separator into a comma and a space */
int i;
for (i = 0; sol[i]; i++) /* print the chars pointed to in sol */
putchar(*sol[i]);
}
}
int main(int argc, char **argv)
{
int opt;
int n = 2; /* default print two digits, as stated in SO question */
/* we use getopt(3) to process a possible option -n to specify the
* actual number of characters we want to print. */
while ((opt = getopt(argc, argv, "n:")) != EOF) {
switch (opt) {
/* option -n allows to select any other length */
case 'n': n = atoi(optarg); break;
}
}
/* initially call the recursive function */
print_numbers(n, alpha, 0);
/* print a last \n so we end in a new line */
puts("");
}
如果运行没有参数，它会打印你发布的样本：
$ asc
01, 02, 03, 04, 05, 06, 07, 08, 09, 12, 13, 14, 15, 16, 17, 18, 19, 23, 24, 25, 26, 27, 28, 29, 34, 35, 36, 37, 38, 39, 45, 46, 47, 48, 49, 56, 57, 58, 59, 67, 68, 69, 78, 79, 89
$ _
或者如果您使用 -n :
$ asc -n 3
012, 013, 014, 015, 016, 017, 018, 019, 023, 024, 025, 026, 027, 028, 029, 034, 035, 036, 037, 038, 039, 045, 046, 047, 048, 049, 056, 057, 058, 059, 067, 068, 069, 078, 079, 089, 123, 124, 125, 126, 127, 128, 129, 134, 135, 136, 137, 138, 139, 145, 146, 147, 148, 149, 156, 157, 158, 159, 167, 168, 169, 178, 179, 189, 234, 235, 236, 237, 238, 239, 245, 246, 247, 248, 249, 256, 257, 258, 259, 267, 268, 269, 278, 279, 289, 345, 346, 347, 348, 349, 356, 357, 358, 359, 367, 368, 369, 378, 379, 389, 456, 457, 458, 459, 467, 468, 469, 478, 479, 489, 567, 568, 569, 578, 579, 589, 678, 679, 689, 789
$ _