-10671---swapsort-'s Introduction
# -10671---swapsort- Description 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 Input The input will be given in main.cpp Output The output will be generated by main.cpp
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. ๐๐๐
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google โค๏ธ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.