## Posted By

dirkchang on 03/28/11

# Combination (no pointer, only array)

/ Published in: C++

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. }