1: //prev_permutation2a.cpp
3: #include <iostream>
4: #include <vector>
5: #include <algorithm>
6: #include <iomanip>
7: using namespace std;
9: /**
10: Tests if one integer has a smaller digit sum than another.
11: Pre:\n i1 and i2 have been initialized and i1, i2 are both > 0.
12: Post:\n Returns true if sum of the digits in i1 is < sum of digits
13: in i2, and otherwise returns false.
14: */
15: bool hasSmallerDigitSum
16: (
17: int i1, //in
18: int i2 //in
19: )
20: {
21: int digitSum1 = 0;
22: while (i1 != 0)
23: {
24: digitSum1 += i1 % 10;
25: i1 /= 10;
26: }
28: int digitSum2 = 0;
29: while (i2 != 0)
30: {
31: digitSum2 += i2 % 10;
32: i2 /= 10;
33: }
34: return digitSum1 < digitSum2;
35: }
37: int main()
38: {
39: cout << "\nThis program illustrates the use of the STL "
40: "prev_permutation() algorithm\n(extended version) to generate "
41: "all permutations of a vector of integers,\nin decreasing order, "
42: "and also to demonstrate what happens to the return\nvalue of the "
43: "algorithm when the \"end\" of a permutation sequence is "
44: "reached\nand we then \"roll over\" to begin a new sequence. "
45: "In this case the order of\nthe integers in a permutation is "
46: "determined by one integer preceding another\nif and only if it "
47: "has a larger digit sum.";
48: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
50: cout << "\nFirst, we declare a vector of 3 integers and show all of "
51: "its permuations.";
52: int a1[] = {17, 25, 51};
53: vector<int> v1(a1, a1+3);
54: cout << "\nHere are the contents of the vector before any "
55: "permutations are generated:\n";
56: for (vector<int>::size_type i=0; i<v1.size(); i++)
57: cout << v1.at(i) << " ";
58: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
60: cout << "\nAnd here are the contents of the vector as each "
61: "permutation is generated:\n";
62: while (prev_permutation(v1.begin(), v1.end(), hasSmallerDigitSum))
63: {
64: for (vector<int>::size_type i=0; i<v1.size(); i++)
65: cout << v1.at(i) << " ";
66: cout << endl;
67: }
68: cout << "Press Enter to continue ... "; cin.ignore(80, '\n');
70: cout << "\nFinally (for this vector), here are its contents"
71: "\nafter all permutations have been generated:\n";
72: for (vector<int>::size_type i=0; i<v1.size(); i++)
73: cout << v1.at(i) << " ";
74: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
76: int a2[] = {55, 25, 51, 17, 11};
77: vector<int> v2(a2, a2+5);
78: cout << "\nHere are the contents of a second vector of 5 integers "
79: "\nbefore any permutations are generated:\n";
80: for (vector<int>::size_type i=0; i<v2.size(); i++)
81: cout << v2.at(i) << " ";
82: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
84: cout << "\nNow we show the return value of the algorithm, and the "
85: "contents of\nthis vector, after each of 6 permutations of just "
86: "the middle 3 values.";
87: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
88: for (int i=1; i<=6; i++)
89: {
90: cout << "Return value: " << boolalpha
91: << prev_permutation(v2.begin()+1, v2.end()-1,
92: hasSmallerDigitSum) << "\t";
93: cout << "Vector contents: ";
94: for (vector<int>::size_type i=0; i<v2.size(); i++)
95: cout << v2.at(i) << " ";
96: cout << endl;
97: }
98: cout << "Press Enter to continue ... "; cin.ignore(80, '\n');
99: }