[已解决]编程求从n数中抽出r个数的所有组合方式 如1234组合为 432 431 421 312

wsx666946

#include<stdio.h>
void Combine(int n,int r,char a[],int  b[],int R)
{
        if(r==0)
        {
                int i=0;
                for(i=0;i<R;i++)
                {
                        printf("%c ",a[b[i]]);
                       
                        }
                printf("\n");
                }
        else
        {
                for(int j=n;j>=r;j--)
                {
                        b[r-1]=j-1;
                        Combine(j-1,r-1,a,b,R+1);
                        }
                }
        }
int main()
{        int n=5,r=3,R=0;
        char a[5]={1,2,3,4,5};
        int b[5];
        Combine(n,r,a,b,R);
}
求大佬们帮忙看看哪里不对 怎么输出不了啊

最佳答案

月排行榜 / 总排行榜

人造人

2022-6-17 19:47:15

不，数组c必须初始化

1. #include <stdio.h>
   
2. 
   
3. void Combine(int n, int r, const int a[const], int b[const], int c[const], int R) {
   
4.     if(R >= r) {
   
5.         for(size_t i = 0; i < R; ++i) {
   
6.             printf("%d ", b[i]);
   
7.         }
   
8.         puts("");
   
9.         return;
   
10.     }
    
11.     for(size_t i = 0; i < n; ++i) {
    
12.         if(c[i]) continue;
    
13.         c[i] = 1;
    
14.         b[R] = a[i];
    
15.         Combine(n, r, a, b, c, R + 1);
    
16.         c[i] = 0;
    
17.     }
    
18. }
    
19. 
    
20. int main(void) {
    
21.     int n = 5, r = 3, R = 0;
    
22.     int a[5] = {1, 2, 3, 4, 5};
    
23.     int b[5];
    
24.     int c[5] = {0};
    
25.     Combine(n, r, a, b, c, R);
    
26. }
    

复制代码

跳转到最佳答案楼层

人造人

不，数组c必须初始化

1. #include <stdio.h>
   
2. 
   
3. void Combine(int n, int r, const int a[const], int b[const], int c[const], int R) {
   
4.     if(R >= r) {
   
5.         for(size_t i = 0; i < R; ++i) {
   
6.             printf("%d ", b[i]);
   
7.         }
   
8.         puts("");
   
9.         return;
   
10.     }
    
11.     for(size_t i = 0; i < n; ++i) {
    
12.         if(c[i]) continue;
    
13.         c[i] = 1;
    
14.         b[R] = a[i];
    
15.         Combine(n, r, a, b, c, R + 1);
    
16.         c[i] = 0;
    
17.     }
    
18. }
    
19. 
    
20. int main(void) {
    
21.     int n = 5, r = 3, R = 0;
    
22.     int a[5] = {1, 2, 3, 4, 5};
    
23.     int b[5];
    
24.     int c[5] = {0};
    
25.     Combine(n, r, a, b, c, R);
    
26. }
    

复制代码

人造人

1. #include <stdio.h>
   
2. 
   
3. void Combine(int n, int r, char a[], int b[], int R) {
   
4.     if(r == 0) {
   
5.         int i = 0;
   
6.         for(i = 0; i < R; i++) {
   
7.             //printf("%c ", a[b[i]]);
   
8.             printf("%hhd ", a[b[i]]);   // 这里不是%c吧？应该是%hhd吧？
   
9.                                         // a数组中的元素类型是signed char
   
10.                                         // signed char应该用%hhd
    
11.         }
    
12.         printf("\n");
    
13.     } else {
    
14.         // 看不懂你这个for循环是在做什么
    
15.         for(int j = n; j >= r; j--) {
    
16.             b[r - 1] = j - 1;
    
17.             Combine(j - 1, r - 1, a, b, R + 1);
    
18.         }
    
19.     }
    
20. }
    
21. 
    
22. int main() {
    
23.     int n = 5, r = 3, R = 0;
    
24.     char a[5] = {1, 2, 3, 4, 5};
    
25.     int b[5];
    
26.     Combine(n, r, a, b, R);
    
27. }
    

复制代码

是要下面这样的效果吗？

1. #include <stdio.h>
   
2. 
   
3. void Combine(int n, int r, const int a[const], int b[], int c[], int R) {
   
4.     if(R >= r) {
   
5.         for(size_t i = 0; i < R; ++i) {
   
6.             printf("%d ", b[i]);
   
7.         }
   
8.         puts("");
   
9.         return;
   
10.     }
    
11.     for(size_t i = 0; i < n; ++i) {
    
12.         if(c[i]) continue;
    
13.         c[i] = 1;
    
14.         b[R] = a[i];
    
15.         Combine(n, r, a, b, c, R + 1);
    
16.         c[i] = 0;
    
17.     }
    
18. }
    
19. 
    
20. int main() {
    
21.     int n = 5, r = 3, R = 0;
    
22.     int a[5] = {1, 2, 3, 4, 5};
    
23.     int b[5];
    
24.     int c[5] = {0};
    
25.     Combine(n, r, a, b, c, R);
    
26. }
    

复制代码

1. $ ./main
   
2. 1 2 3
   
3. 1 2 4
   
4. 1 2 5
   
5. 1 3 2
   
6. 1 3 4
   
7. 1 3 5
   
8. 1 4 2
   
9. 1 4 3
   
10. 1 4 5
    
11. 1 5 2
    
12. 1 5 3
    
13. 1 5 4
    
14. 2 1 3
    
15. 2 1 4
    
16. 2 1 5
    
17. 2 3 1
    
18. 2 3 4
    
19. 2 3 5
    
20. 2 4 1
    
21. 2 4 3
    
22. 2 4 5
    
23. 2 5 1
    
24. 2 5 3
    
25. 2 5 4
    
26. 3 1 2
    
27. 3 1 4
    
28. 3 1 5
    
29. 3 2 1
    
30. 3 2 4
    
31. 3 2 5
    
32. 3 4 1
    
33. 3 4 2
    
34. 3 4 5
    
35. 3 5 1
    
36. 3 5 2
    
37. 3 5 4
    
38. 4 1 2
    
39. 4 1 3
    
40. 4 1 5
    
41. 4 2 1
    
42. 4 2 3
    
43. 4 2 5
    
44. 4 3 1
    
45. 4 3 2
    
46. 4 3 5
    
47. 4 5 1
    
48. 4 5 2
    
49. 4 5 3
    
50. 5 1 2
    
51. 5 1 3
    
52. 5 1 4
    
53. 5 2 1
    
54. 5 2 3
    
55. 5 2 4
    
56. 5 3 1
    
57. 5 3 2
    
58. 5 3 4
    
59. 5 4 1
    
60. 5 4 2
    
61. 5 4 3
    
62. $

复制代码

人造人

1. #include <stdio.h>
   
2. 
   
3. void Combine(int n, int r, const int a[const], int b[const], int c[const], int R) {
   
4.     if(R >= r) {
   
5.         for(size_t i = 0; i < R; ++i) {
   
6.             printf("%d ", b[i]);
   
7.         }
   
8.         puts("");
   
9.         return;
   
10.     }
    
11.     for(size_t i = 0; i < n; ++i) {
    
12.         if(c[i]) continue;
    
13.         c[i] = 1;
    
14.         b[R] = a[i];
    
15.         Combine(n, r, a, b, c, R + 1);
    
16.         c[i] = 0;
    
17.     }
    
18. }
    
19. 
    
20. int main(void) {
    
21.     int n = 5, r = 3, R = 0;
    
22.     int a[5] = {1, 2, 3, 4, 5};
    
23.     int b[5];
    
24.     int c[5] = {0};
    
25.     Combine(n, r, a, b, c, R);
    
26. }
    

复制代码

人造人

再改一下

1. #include <stdio.h>
   
2. 
   
3. void Combine(int n, int r, const int a[const], int b[const], int c[const], int R) {
   
4.     if(R >= r) {
   
5.         for(size_t i = 0; i < R; ++i) {
   
6.             printf("%d ", b[i]);
   
7.         }
   
8.         puts("");
   
9.         return;
   
10.     }
    
11.     for(size_t i = 0; i < n; ++i) {
    
12.         if(c[i]) continue;
    
13.         c[i] = 1;
    
14.         b[R] = a[i];
    
15.         Combine(n, r, a, b, c, R + 1);
    
16.         c[i] = 0;
    
17.     }
    
18. }
    
19. 
    
20. int main(void) {
    
21.     int n = 5, r = 3, R = 0;
    
22.     int a[5] = {1, 2, 3, 4, 5};
    
23.     int b[5];
    
24.     int c[5];
    
25.     Combine(n, r, a, b, c, R);
    
26. }
    

复制代码

wsx666946

人造人 发表于 2022-6-17 20:32
不，数组c必须初始化

我明白了是因为我定义字符数组的时候定义错了，应该是char a[5]={'1','2','3','4','5'}; 或者char a[5]="12345";

wsx666946

人造人 发表于 2022-6-17 20:23
是要下面这样的效果吗？

我第二个循环是用数组b来存储组合数中每个数字在待组合数数组a中的下标

人造人

wsx666946 发表于 2022-6-17 20:42
我第二个循环是用数组b来存储组合数中每个数字在待组合数数组a中的下标

那么这5个数选3个进行组合，结果是什么？
12345

这个？

1. $ ./main
   
2. 1 2 3
   
3. 1 2 4
   
4. 1 2 5
   
5. 1 3 2
   
6. 1 3 4
   
7. 1 3 5
   
8. 1 4 2
   
9. 1 4 3
   
10. 1 4 5
    
11. 1 5 2
    
12. 1 5 3
    
13. 1 5 4
    
14. 2 1 3
    
15. 2 1 4
    
16. 2 1 5
    
17. 2 3 1
    
18. 2 3 4
    
19. 2 3 5
    
20. 2 4 1
    
21. 2 4 3
    
22. 2 4 5
    
23. 2 5 1
    
24. 2 5 3
    
25. 2 5 4
    
26. 3 1 2
    
27. 3 1 4
    
28. 3 1 5
    
29. 3 2 1
    
30. 3 2 4
    
31. 3 2 5
    
32. 3 4 1
    
33. 3 4 2
    
34. 3 4 5
    
35. 3 5 1
    
36. 3 5 2
    
37. 3 5 4
    
38. 4 1 2
    
39. 4 1 3
    
40. 4 1 5
    
41. 4 2 1
    
42. 4 2 3
    
43. 4 2 5
    
44. 4 3 1
    
45. 4 3 2
    
46. 4 3 5
    
47. 4 5 1
    
48. 4 5 2
    
49. 4 5 3
    
50. 5 1 2
    
51. 5 1 3
    
52. 5 1 4
    
53. 5 2 1
    
54. 5 2 3
    
55. 5 2 4
    
56. 5 3 1
    
57. 5 3 2
    
58. 5 3 4
    
59. 5 4 1
    
60. 5 4 2
    
61. 5 4 3
    
62. $

复制代码

wsx666946

人造人 发表于 2022-6-17 20:50
那么这5个数选3个进行组合，结果是什么？
12345

3 4 5
2 4 5
1 4 5
2 3 5
1 3 5
1 2 5
2 3 4
1 3 4
1 2 4
1 2 3

[Program finished]
书上的结果是这个 每次抽三个数 组合是没有顺序之分的

人造人

wsx666946 发表于 2022-6-17 20:55
3 4 5
2 4 5
1 4 5

哦

桃花飞舞

排列组合还有顺序之分么？没这要求吧？

傻眼貓咪

桃花飞舞 发表于 2022-6-18 00:43
排列组合还有顺序之分么？没这要求吧？

应该是不重复意思，比如：{1, 2, 5} 和 {5, 1, 2} 和 {2, 5, 1} 相同。
所谓的顺序应该是指位置顺序吧。

Combination 组合（位置无分顺序）和 Permutation 排列 （位置讲究顺序）

傻眼貓咪

人造人 发表于 2022-6-17 20:59
哦

你的代码思路很厉害学习学习

可以试试另外附加一个打印条件就完成楼主要的结果了。

打印条件需符合：打印下一个目标必须大于等于之前目标，便可以滤过重复性的打印了

桃花飞舞

傻眼貓咪 发表于 2022-6-18 08:17
应该是不重复意思，比如：{1, 2, 5} 和 {5, 1, 2} 和 {2, 5, 1} 相同。
所谓的顺序应该是指位置顺序吧 ...

虽然知道这是用递归的方法做的，但是还是不懂它是怎么把原问题分解为子问题的，是先取0个看有几种解法，再取1个看有几种解法，然后再取2个看有几种解法么？原问题是在5个里取3个看有几种取法？

傻眼貓咪

桃花飞舞 发表于 2022-6-18 13:15
虽然知道这是用递归的方法做的，但是还是不懂它是怎么把原问题分解为子问题的，是先取0个看有几种解法， ...

如果是题目只要求算出有几种解法相对简单很多，只需要用公式就可以算出，不用递归。

至于想打印所有组合，楼上人造人大佬已经题解了。

桃花飞舞

傻眼貓咪 发表于 2022-6-18 16:29
如果是题目只要求算出有几种解法相对简单很多，只需要用公式就可以算出，不用递归。

至于想打印所有组 ...

嗯，真搞不懂楼主的方法为什么也对，b[r-1] = j - 1;为什么要这么一句？从

1. a[b[i]]

复制代码

可以知道

1. b[i]

复制代码

是a的索引，而b[0] = 2; b[1] = 3; b[2] = 4; 也就是a[2]=3; a[3] = 4; a[4] = 5;搞不懂怎么会打印出10种组合出来？应该是for循环的原因，感觉复杂，只可惜看不懂人造人的代码

人造人

傻眼貓咪 发表于 2022-6-18 09:55
你的代码思路很厉害学习学习

可以试试另外附加一个打印条件就完成楼主要的结果了。

感觉这样写不是很好，我也没有更好的方法了

1. $ cat main.c
   
2. #include <stdio.h>
   
3. 
   
4. void Combine(int n, int r, const int a[const], int b[const], int R) {
   
5.     if(r <= 0) {
   
6.         for(size_t i = 0; i < R; ++i) {
   
7.             printf("%d ", b[i]);
   
8.         }
   
9.         puts("");
   
10.         return;
    
11.     }
    
12.     for(size_t i = 0; i < n; ++i) {
    
13.         b[R] = a[i];
    
14.         Combine(n - 1 - i, r - 1, a + 1 + i, b, R + 1);
    
15.     }
    
16. }
    
17. 
    
18. int main(void) {
    
19.     int n = 5, r = 3, R = 0;
    
20.     int a[5] = {1, 2, 3, 4, 5};
    
21.     int b[5];
    
22.     Combine(n, r, a, b, R);
    
23. }
    
24. $ gcc-debug -o main main.c
    
25. $ ./main
    
26. 1 2 3
    
27. 1 2 4
    
28. 1 2 5
    
29. 1 3 4
    
30. 1 3 5
    
31. 1 4 5
    
32. 2 3 4
    
33. 2 3 5
    
34. 2 4 5
    
35. 3 4 5
    
36. $
    

复制代码

人造人

傻眼貓咪 发表于 2022-6-18 09:55
你的代码思路很厉害学习学习

可以试试另外附加一个打印条件就完成楼主要的结果了。

要么就再加一个变量，记录下一层从哪个位置开始遍历

1. $ cat main.c
   
2. #include <stdio.h>
   
3. 
   
4. void Combine(int n, int r, const int a[const], int b[const], int R, size_t c) {
   
5.     if(r <= 0) {
   
6.         for(size_t i = 0; i < R; ++i) {
   
7.             printf("%d ", b[i]);
   
8.         }
   
9.         puts("");
   
10.         return;
    
11.     }
    
12.     for(size_t i = c; i < n; ++i) {
    
13.         b[R] = a[i];
    
14.         Combine(n, r - 1, a, b, R + 1, i + 1);
    
15.     }
    
16. }
    
17. 
    
18. int main(void) {
    
19.     int n = 5, r = 3, R = 0;
    
20.     int a[5] = {1, 2, 3, 4, 5};
    
21.     int b[5];
    
22.     Combine(n, r, a, b, R, 0);
    
23. }
    
24. $ gcc-debug -o main main.c
    
25. $ ./main
    
26. 1 2 3
    
27. 1 2 4
    
28. 1 2 5
    
29. 1 3 4
    
30. 1 3 5
    
31. 1 4 5
    
32. 2 3 4
    
33. 2 3 5
    
34. 2 4 5
    
35. 3 4 5
    
36. $
    

复制代码

当然楼主那种从后往前遍历也可以

1. $ cat main.c
   
2. #include <stdio.h>
   
3. 
   
4. void Combine(int n, int r, const int a[const], int b[const], int R) {
   
5.     if(r <= 0) {
   
6.         for(size_t i = 0; i < R; ++i) {
   
7.             printf("%d ", b[i]);
   
8.         }
   
9.         puts("");
   
10.         return;
    
11.     }
    
12.     for(ssize_t i = n - 1; i >= 0; --i) {
    
13.         b[R] = a[i];
    
14.         Combine(i, r - 1, a, b, R + 1);
    
15.     }
    
16. }
    
17. 
    
18. int main(void) {
    
19.     int n = 5, r = 3, R = 0;
    
20.     int a[5] = {1, 2, 3, 4, 5};
    
21.     int b[5];
    
22.     Combine(n, r, a, b, R);
    
23. }
    
24. $ gcc-debug -o main main.c
    
25. $ ./main
    
26. 5 4 3
    
27. 5 4 2
    
28. 5 4 1
    
29. 5 3 2
    
30. 5 3 1
    
31. 5 2 1
    
32. 4 3 2
    
33. 4 3 1
    
34. 4 2 1
    
35. 3 2 1
    
36. $
    

复制代码

人造人

桃花飞舞 发表于 2022-6-18 16:53
嗯，真搞不懂楼主的方法为什么也对，b[r-1] = j - 1;为什么要这么一句？从可以知道是a的索引，而b[0] = ...

的确楼主的方法复杂了，其实不需要保存索引，直接保存值就可以