| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10687 | swap & extend |
|
Description
Given an integer sequence, say {6, 1, 4, 3, 5, 2}, we can choose any pair of two neighboring numbers (in a circular sense) and swap them to generate a new sequence. For example,
If we choose 6 and 2, we get {2, 1, 4, 3, 5, 6} after swapping.
If we choose 1 and 4, we get {6, 4, 1, 3, 5, 2} after swapping.
Try to generate all possible results from the original sequence, and print the results in lexicographical order. For the example above, the output would be
1 6 4 3 5 2
2 1 4 3 5 6
6 1 3 4 5 2
6 1 4 3 2 5
6 1 4 5 3 2
6 4 1 3 5 2
Hint: 1. Use the set and vector containers. 2. The items in a set will be automatically sorted in lexicographical order.
The framework of main.cpp is provided for you.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
// Define "extend" here.
// set<vector<int>> extend(vector<int> v)
int main()
{
vector<int> v; // = {6, 1, 4, 3, 5, 2};
int e;
while (cin >> e) { // press Ctrl + Z to end the input
v.push_back(e);
}
auto S = extend(v); // the type of S will depend on the return type of extend
for (auto s : S) {
cout << s[0];
for (unsigned i=1; i<s.size(); ++i) {
cout << " " << s[i];
}
cout << "\n";
}
}
Notice1. This exam is in normal judge, so you need to submit the main.cpp only.
Notice2. You are not allowed modifying code in main(). Just implement the function extend().
Input
The sequence of numbers. EOF at the end.
Output
The output is generated by main.cpp