高手进来:如何用C语言编写一个数字组合问题,即在给定个数的数字中列出其所有组合

Question

例如1,2,3,4取一个有1,2,3,4四种,取两有C24=4*3=12种;取三个有C34=4种;取四个有C44=1种,即在给定个数的数字中列出其所有可能的组合
多谢指出,是我算错了,C24=4*3/(2*1)=6,不过指问题要有一般性,给定数字的个数不确定,要用C语言写

Answer 1

纠正一下: C24 = 4!/2!/2! = 6

n,m 是可以任意输入的,你还要什么一般性?

n, m = 4 2
1 : 1 2
2 : 1 3
3 : 1 4
4 : 2 3
5 : 2 4
6 : 3 4
Press any key to continue

#include<iostream>
using namespace std;

int N = 1;

void print(int a[], int n) {
cout<<' '<<N++<<" : ";
for (int i = 0; i < n; i++)
cout<<a[i]<<' ';
cout<<endl;
}

void swap(int &a, int &b) {
int t = a;
a = b;
b = t;
}//交换

void reverse(int a[], int i, int j) {
while (i<j) {
swap(a[i++],a[j--]);
}
}//颠倒

f(int a[], int n) {
for (int i = 0; i < n-1; i++)
if(a[i] > a[i+1])
return 0;
return 1;
}

void main() {
int *a, i, j, n, m;
cout<<" n, m = ";
cin>>n>>m;
a = new int[n];
for (i = 0; i < n; i++)
a[i] = i + 1;
i = m - 1;
while (1) {
if(i+1 == m && f(a, m)) {
print(a, m);
}
for (i=n-2; i>=0; i--)
if (a[i] < a[i+1]) break;
if (i==-1) break;
for (j=n-1; j>i; j--)
if (a[j] > a[i]) break;
swap(a[i],a[j]);
reverse(a,i+1,n-1);
}
}

C语言版:
#include<stdio.h>

int N = 1;

void print(int a[], int n) {
printf(" %d : ", N++);
for (int i = 0; i < n; i++)
printf("%2d",a[i]);
putchar('\n');
}

void swap(int &a, int &b) {
int t = a;
a = b;
b = t;
}//交换

void reverse(int a[], int i, int j) {
while (i<j) {
swap(a[i++],a[j--]);
}
}//颠倒

f(int a[], int n) {
for (int i = 0; i < n-1; i++)
if(a[i] > a[i+1])
return 0;
return 1;
}

void main() {
int *a, i, j, n, m;
printf(" n, m = ");
scanf("%d%d",&n,&m);
a = new int[n];
for (i = 0; i < n; i++)
a[i] = i + 1;
i = m - 1;
while (1) {
if(i+1 == m && f(a, m)) {
print(a, m);
}
for (i=n-2; i>=0; i--)
if (a[i] < a[i+1]) break;
if (i==-1) break;
for (j=n-1; j>i; j--)
if (a[j] > a[i]) break;
swap(a[i],a[j]);
reverse(a,i+1,n-1);
}
}

Answer 2

用深度优先算法，递归。算法可在网上搜“组合生成算法”，或找面向计算机的组合数学书，或Knuth的《具体数学》等书。
http://blog.programfan.com/article.asp?id=16993

Answer 3

最直观的穷举法

给出选取参数

然后用循环去穷举，用递归也可以，不过难以理解