chungkuoyen / -10671---swapsort- Goto Github PK

# -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