[已解决]编程求从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必须初始化

#include <stdio.h>

void Combine(int n, int r, const int a[const], int b[const], int c[const], int R) {
    if(R >= r) {
        for(size_t i = 0; i < R; ++i) {
            printf("%d ", b[i]);
        }
        puts("");
        return;
    }
    for(size_t i = 0; i < n; ++i) {
        if(c[i]) continue;
        c[i] = 1;
        b[R] = a[i];
        Combine(n, r, a, b, c, R + 1);
        c[i] = 0;
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int b[5];
    int c[5] = {0};
    Combine(n, r, a, b, c, R);
}

跳转到最佳答案楼层

人造人

不，数组c必须初始化

#include <stdio.h>

void Combine(int n, int r, const int a[const], int b[const], int c[const], int R) {
    if(R >= r) {
        for(size_t i = 0; i < R; ++i) {
            printf("%d ", b[i]);
        }
        puts("");
        return;
    }
    for(size_t i = 0; i < n; ++i) {
        if(c[i]) continue;
        c[i] = 1;
        b[R] = a[i];
        Combine(n, r, a, b, c, R + 1);
        c[i] = 0;
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int b[5];
    int c[5] = {0};
    Combine(n, r, a, b, c, R);
}

人造人

#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("%hhd ", a[b[i]]);   // 这里不是%c吧？应该是%hhd吧？
                                        // a数组中的元素类型是signed char
                                        // signed char应该用%hhd
        }
        printf("\n");
    } else {
        // 看不懂你这个for循环是在做什么
        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);
}

是要下面这样的效果吗？

#include <stdio.h>

void Combine(int n, int r, const int a[const], int b[], int c[], int R) {
    if(R >= r) {
        for(size_t i = 0; i < R; ++i) {
            printf("%d ", b[i]);
        }
        puts("");
        return;
    }
    for(size_t i = 0; i < n; ++i) {
        if(c[i]) continue;
        c[i] = 1;
        b[R] = a[i];
        Combine(n, r, a, b, c, R + 1);
        c[i] = 0;
    }
}

int main() {
    int n = 5, r = 3, R = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int b[5];
    int c[5] = {0};
    Combine(n, r, a, b, c, R);
}

$ ./main
1 2 3
1 2 4
1 2 5
1 3 2
1 3 4
1 3 5
1 4 2
1 4 3
1 4 5
1 5 2
1 5 3
1 5 4
2 1 3
2 1 4
2 1 5
2 3 1
2 3 4
2 3 5
2 4 1
2 4 3
2 4 5
2 5 1
2 5 3
2 5 4
3 1 2
3 1 4
3 1 5
3 2 1
3 2 4
3 2 5
3 4 1
3 4 2
3 4 5
3 5 1
3 5 2
3 5 4
4 1 2
4 1 3
4 1 5
4 2 1
4 2 3
4 2 5
4 3 1
4 3 2
4 3 5
4 5 1
4 5 2
4 5 3
5 1 2
5 1 3
5 1 4
5 2 1
5 2 3
5 2 4
5 3 1
5 3 2
5 3 4
5 4 1
5 4 2
5 4 3
$ 

人造人

#include <stdio.h>

void Combine(int n, int r, const int a[const], int b[const], int c[const], int R) {
    if(R >= r) {
        for(size_t i = 0; i < R; ++i) {
            printf("%d ", b[i]);
        }
        puts("");
        return;
    }
    for(size_t i = 0; i < n; ++i) {
        if(c[i]) continue;
        c[i] = 1;
        b[R] = a[i];
        Combine(n, r, a, b, c, R + 1);
        c[i] = 0;
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int b[5];
    int c[5] = {0};
    Combine(n, r, a, b, c, R);
}

人造人

再改一下

#include <stdio.h>

void Combine(int n, int r, const int a[const], int b[const], int c[const], int R) {
    if(R >= r) {
        for(size_t i = 0; i < R; ++i) {
            printf("%d ", b[i]);
        }
        puts("");
        return;
    }
    for(size_t i = 0; i < n; ++i) {
        if(c[i]) continue;
        c[i] = 1;
        b[R] = a[i];
        Combine(n, r, a, b, c, R + 1);
        c[i] = 0;
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int b[5];
    int c[5];
    Combine(n, r, a, b, c, R);
}

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

这个？

$ ./main
1 2 3
1 2 4
1 2 5
1 3 2
1 3 4
1 3 5
1 4 2
1 4 3
1 4 5
1 5 2
1 5 3
1 5 4
2 1 3
2 1 4
2 1 5
2 3 1
2 3 4
2 3 5
2 4 1
2 4 3
2 4 5
2 5 1
2 5 3
2 5 4
3 1 2
3 1 4
3 1 5
3 2 1
3 2 4
3 2 5
3 4 1
3 4 2
3 4 5
3 5 1
3 5 2
3 5 4
4 1 2
4 1 3
4 1 5
4 2 1
4 2 3
4 2 5
4 3 1
4 3 2
4 3 5
4 5 1
4 5 2
4 5 3
5 1 2
5 1 3
5 1 4
5 2 1
5 2 3
5 2 4
5 3 1
5 3 2
5 3 4
5 4 1
5 4 2
5 4 3
$ 

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;为什么要这么一句？从

a[b[i]]

可以知道

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
你的代码思路很厉害学习学习

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

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

$ cat main.c
#include <stdio.h>

void Combine(int n, int r, const int a[const], int b[const], int R) {
    if(r <= 0) {
        for(size_t i = 0; i < R; ++i) {
            printf("%d ", b[i]);
        }
        puts("");
        return;
    }
    for(size_t i = 0; i < n; ++i) {
        b[R] = a[i];
        Combine(n - 1 - i, r - 1, a + 1 + i, b, R + 1);
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int b[5];
    Combine(n, r, a, b, R);
}
$ gcc-debug -o main main.c
$ ./main
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
$

人造人

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

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

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

$ cat main.c
#include <stdio.h>

void Combine(int n, int r, const int a[const], int b[const], int R, size_t c) {
    if(r <= 0) {
        for(size_t i = 0; i < R; ++i) {
            printf("%d ", b[i]);
        }
        puts("");
        return;
    }
    for(size_t i = c; i < n; ++i) {
        b[R] = a[i];
        Combine(n, r - 1, a, b, R + 1, i + 1);
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int b[5];
    Combine(n, r, a, b, R, 0);
}
$ gcc-debug -o main main.c
$ ./main
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
$

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

$ cat main.c
#include <stdio.h>

void Combine(int n, int r, const int a[const], int b[const], int R) {
    if(r <= 0) {
        for(size_t i = 0; i < R; ++i) {
            printf("%d ", b[i]);
        }
        puts("");
        return;
    }
    for(ssize_t i = n - 1; i >= 0; --i) {
        b[R] = a[i];
        Combine(i, r - 1, a, b, R + 1);
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int b[5];
    Combine(n, r, a, b, R);
}
$ gcc-debug -o main main.c
$ ./main
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
$

人造人

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

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