Given an integer sequence, say {6, 1, 3, 4, 5, 2}, can we sort the sequence by keeping swapping the first number with its two neighbors: the second number and the last number. For example,
Swap 6 and 2 to get {2, 1, 3, 4, 5, 6}, and then swap 2 and 1 to get
{1, 2, 3, 4, 5, 6}, and we get the sequence sorted.
In function.h we define a class called SwapSort. A constructor and a member function show_solutions are implemented. Your task is to complete the implementation of the following two functions:
1. set<State> extend(State s);
A state is defined as using State = vector<int>;
For some state s, we may extend it by swapping the first number with the second one, or swapping the first number with the last one. Therefore, from state s we may generate two new states, and insert them into a set.
2. void solve(int steps);
This function tries to solve the problem in a number of swaps specified by steps. The found solutions are stored in the class member set<list<State>> _solutions;
You need to implement the two functions in function.cpp
sample code of main.cpp
#include "function.h"
int main()
{
State s = {2, 1, 3};
SwapSort prob1(s);
prob1.solve(4);
prob1.show_solutions();
cout << "\n";
State t = {6, 1, 3, 4, 5, 2};
SwapSort prob2(t);
prob2.solve(4);
prob2.show_solutions();
cout << "\n";
State r = {2, 1, 3, 5, 4};
SwapSort prob3(r);
prob3.solve(4);
prob3.show_solutions();
cout << "\n";
}
code of function.h
#ifndef _SWAPSORT_
#define _SWAPSORT_
#include <iostream>
#include <vector>
#include <set>
#include <list>
#include <algorithm>
using namespace std;
using State = vector<int>;
class SwapSort
{
private:
set<list<State>> _paths;
set<list<State>> _solutions;
set<State> _explored;
public:
SwapSort(State init)
{
list<State> ls;
ls.push_back(init);
_paths.insert(ls);
}
void show_solutions()
{
if (_solutions.size()==0) {
cout << "No solution.\n";
} else {
for (auto p : _solutions) {
for (auto s : p) {
for (auto i : s) {
cout << i << " ";
}
cout << "-> ";
}
cout << ".\n";
}
}
}
set<State> extend(State s);
void solve(int steps);
};
#endif
The input will be given in main.cpp
The output will be generated by main.cpp