简单的排列和组合

你就别嘲我了，既然简单，就把程序拿出来！！

PS：组合我会的呀，就是全排列了！！

分数伺候！我要将这些排列都打印出来的，不是计算个数！！[em9][em9]

#include<iostream>

template <class T> void perm(T [], int, int);

int main()
{
    int list[] = {1, 2, 3, 4, 5};
    perm(list, 0, 4);
}

template <class T>
void swap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}

template <class T>
void perm(T list[], int k, int m)
{
    if(m == k)
    {
        for(int i = 0; i <= m; i++)
            std::cout << list[i] << " ";
        std::cout << std::endl;
    }
    else
        for(int i = k; i <= m; i++)
        {
            swap(list[k], list[i]);
            perm(list, k + 1, m);
            swap(list[k], list[i]);
        }
}


/**********************

OUTPUT :

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

**********************/

以上c++版。。。仅提供算法。。。其他语言类似

我说了，分数上不会亏待你的！！

谢拉！

……您，会pascal吗？我看不懂！！

PS:c++我只会一点点。

哈，我们学校搞OI的都用P语言，就我用C，感觉C比较灵活，所以开始就没学过P

大概说下思路了：

总的来说是递归的思路，
设所有要排列的n个元素为 r1,r2,r3,...rn,它们的集合为R (R={r1,r2,r3...rn})
规定对于集合R的全排列是Perm(R)

当n=1时，Perm(R) = r1，只有r1一个元素
当n>1时，Perm(R)全排列由 (r1)Perm(R-r1), (r2)Perm(R-r2), (r3)Perm(R-r3),...(rn)Perm(R-rn) 构成

伪代码:

1、list[n]表示数组，n是下标，//...表示注释，int是整型变量,Type表示待排列元素的类型

2、函数perm中，参数list是要排列的元素数组，k,m确定排列范围，
即排列 list[k] ... list[m] 之间的元素

perm(Type list[], int k, int m)
{
    if m = k then    //n=1的情况,只剩下一个元素
        for i = 0 to m
            输出 << list[i] << " "
        输出 << 换行
    else    //n>1的情况,还有多个元素待排列,递归求解
        for i = k to m
            swap(list[k], list[i]);
            perm(list, k + 1, m);    //递归
            swap(list[k], list[i]);
        end{for}
    end{if}
}

定义swap(交换2元素)

void swap(Type &a, Type &b)
{
    T temp = a;
    a = b;
    b = temp;
}

谢谢，可我最多只能打10分了，一个人在一个主题中得分不超过50，不是吗？

呵呵，你这个思路很有创意，能说说怎么想到的么？？[em12][em12]