回 帖 发 新 帖 刷新版面

主题:[原创]打印组合数,不是排列喔

有很多文章讨论如何打印全排列的,毕竟它是很多遍历问题的基础嘛。这里介绍的是如何打印组合数。
先看一个例子:
            C(5,3) = 10
               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

大家注意到没有,
 [color=00FF00]              1 | 2 3
               1 | 2 4
               1 | 2 5
               1 | 3 4
               1 | 3 5
               1 | 4 5[/color] 
              ------ C(4, 2)∵可以在{2, 3, 4, 5}中挑2个出来。
           [color=FF00FF]    2 | 3 4
               2 | 3 5
               2 | 4 5[/color] 
              ------ C(3, 2)∵可以在{3, 4, 5}中挑2个出来。
             [color=FF0000]  3 | 4 5[/color] 
              ------ C(2, 2)∵只能在{4, 5}中挑2个出来。
               
这样就很容易写出递归算法来。
Algorithm [i][size=3]combination[/size][/i](n, k, A[l..n+l-1])
1.        if k = 0
2.            print ary[1..k]
3.        else 
4.            for i←1 to n-k+1
5.                ary[[color=FF0000]index++] [/color]= A[l+i-1]
6.                combination(n-i, k-1, A[l+i..n+l-1])
7.                [color=FF00FF]--index[/color]
8.            endfor
            
大家可能会疑惑干嘛要弄出个index,还有一加一减的(你手工算一下就知道了)。

可以在pku acm 2245 Lotto 上试一试。

附:

# include <iostream>
# include <vector>
using namespace std;

const int N = 100;
int ary[N];
void print(const int ary[], int l, int r)
{
    for (int i = l; i <= r; ++i) {
        cout << ary[i] << " ";
    }
    cout << endl;
}

int _C(int n, int k, vector<int> A, int l, const int lll, const int kkk, int &index)
{
    if (k == 0) {
        print(ary, lll, kkk);
        return 1;
    }
    int count = 0;
    for (int i = 1; i <= n - k + 1; ++i) {
        ary[index++] = A[l + i - 1];
        count += _C(n - i, k - 1, A, l + i, lll, kkk, index);
        --index;
    }
    return count;
}

int combination(int n, int k)
// 只是为了封装
{
    vector<int> v;
    v.push_back(0);
    for (int j = 1; j <= n; ++j) {
        v.push_back(j);
    }
    int index = 1;
    return _C(n, k, v, 1, 1, k, index);
}

int main()
{
    int n = 5, w = 3;
    cout << combination(n, w) << endl;
    return 0;
}

[url=http://blog.csdn.net/Sedgewick]感兴趣的来我的窝看看。[/url]

回复列表 (共1个回复)

沙发

如果是全排列,STL提供了很好的函数 next_permutation():
[color=00FF00]template <class BidirectionalIterator>
  bool [color=0000FF]next_permutation[/color] (BidirectionalIterator first,
                         BidirectionalIterator last );

template <class BidirectionalIterator, class Compare>
  bool [color=C0C0C0]next_permutation[/color] (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);[/color]

[color=0000FF]Example[/color]
// next_permutation
#include <iostream>
#include <algorithm>
using namespace std;

int main () {
  int myints[] = {1,2,3};

  cout << "The 3! possible permutations with 3 elements:\n";

  sort (myints,myints+3);

  do {
    cout << myints[0] << " " << myints[1] << " " << myints[2] << endl;
  } while ( [color=FF0000]next_permutation [/color](myints,myints+3) );

  return 0;
}
 

[color=0000FF]Output:[/color]
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 

我来回复

您尚未登录,请登录后再回复。点此登录或注册