Advanced Search

Combination (no pointer, only array)

/ Published in: C++
Save to your folder(s)

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. /*
  2.  * combination.cpp
  3.  *
  4.  *  Created on: 2011/3/25
  5.  *      Author: dirk
  6.  */
  7. // for convenience, indexing in this alg. starts from 1
  8.  
  9. #include <iostream>
  10. using namespace std;
  11.  
  12. #define MAX 512
  13.  
  14. inline int advance_and_relax(int digits[], int m, int n) {
  15.     if(n == 1) return 0; // no way to advance
  16.     for(int i = n - 1; i >= 1; --i) {
  17.         if(++digits[i] <= (m - n + i)) { // digits[i] is able to advance
  18.             for(int cur_index = i+1, cur_value = digits[i]+1; cur_index <= n; ++cur_index) { // we relax all digits behind digits[i]
  19.                 digits[cur_index] = cur_value++;
  20.             }   
  21.             return 1;
  22.         }   
  23.     }   
  24.     return 0;
  25. }
  26.  
  27. inline void C(int x[], int m, int n) {
  28.     int digits[MAX+1]; // our indexing starts from 1
  29.     for(int i = 0; i < n + 1; ++i) digits[i] = i; // initialization
  30.     int finish = 0;
  31.     while(finish == 0) {
  32.         for(int i = 1; i <= n; ++i) cout << x[digits[i]] << ' ';
  33.         cout << '\n';
  34.         if(++digits[n] > m) {
  35.             if(advance_and_relax(digits, m, n) == 1) finish = 0;
  36.             else finish = 1;
  37.         }   
  38.     }   
  39. }
  40.  
  41. int main() {
  42.     int m, n;
  43.     int x[MAX+1];
  44.     cout << "M = ? ";
  45.     cin >> m;
  46.     cout << "N = ? ";
  47.     cin >> n;
  48.     cout << "輸入 M 個數字: ";
  49.     for(int i = 1; i <= m; ++i) cin >> x[i];
  50.     if(m < n || m <=0 || n <= 0 || m > 512) {
  51.         cout << "輸入格式不正確, 界線條件是 M > N 且 M, N > 0\n"
  52.              << "記憶體限制是 M 必須小於等於 512\n"
  53.              << "真的 M 太大也會算很久怕你沒耐心XD\n";
  54.         return -1;
  55.     }
  56.     C(x, m, n);
  57. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.