好像是置换群的问题
给出1到n的一个排列 (注意是 环) ,每次只能相邻的两的元素交换
问排出从小到大的序 最小需要几次交换
n<=10
我想了两种算法
1> 搜索+康托展开判重
时间是10!*(10^2),好像在超时的边缘
2>
枚举这个环的起始位置,变成一条链,再冒泡排序,记录每次冒泡的最小值
这种做法总是WA
请问有什么好的做法??
谢谢
[解决办法]
冒泡
#include "iostream"using namespace std;int bubble(int a[], int num){ int swap_cnt = 0; for (int i = 0; i < num; ++i) for (int j = num - 1; j > i; --j) if (a[j] < a[j - 1]) { swap(a[j], a[j - 1]); ++swap_cnt; } return swap_cnt;}const int max_num = 10;int main(){ int data[max_num]; int temp[max_num]; int num = 0; cin>>num; if (num <= 0 || num > 10) return 1; for (int i = 0; i < num; ++i) cin>>data[i]; int swap_cnt = num * num; for (int i = 0; i < num; ++i) { for (int j = 0; j < num; ++j) temp[j] = data[(j + i) % num]; int cnt = bubble(temp, num); if (cnt < swap_cnt) swap_cnt = cnt; } cout<<swap_cnt<<endl; return 0;}------------------103 4 5 6 7 8 9 2 1 03
[解决办法]
#include <algorithm>#include <vector>#include <deque>#include <cstdio>using namespace std;struct smaller{ int m_n; smaller(int n) : m_n(n) { } bool operator() (int n) { return n < m_n; }};template <typename iter>int count_range(iter first, iter last){ if (first == last) return 0; int t = 1, n = 1, s = 0; for (iter i = last - 1; i != first; t *= ++n) { --i; s += t * count_if(i, last, smaller(*i)); } return s;}int main(int argc, char* argv[]){ if (argc < 4) { printf ("need at least 3 numbers\n"); return -1; } else if (argc > 11) { printf ("need at most 10 numbers\n"); return -1; } vector<int> v; for (int i = 1; i < argc; ++i) { int n; if (sscanf(argv[i], "%d", &n) == 0) { printf ("%s is not a number\n", argv[i]); return -1; } v.push_back(n); } rotate(v.begin(), find(v.begin(), v.end(), 1), v.end()); int target = count_range(v.begin() + 1, v.end()); printf ("target: %d\n", target); if (target == 0) { printf ("step: 0\n"); return 0; } size_t total = 1; for (size_t i = 2; i < v.size(); ++i) total *= i; sort(v.begin(), v.end()); vector<int> arr(total, 0); deque<vector<int> > work; work.push_back(vector<int>(v.begin() + 1, v.end())); vector<int> s = v; while (!work.empty()) { vector<int> w = work.front(); work.pop_front(); int c = count_range(w.begin(), w.end()); int m = arr[c]; size_t ws = w.size(); size_t e = ws - 1; for (size_t i = 0; i <= w.size(); ++i) { if (i < e) iter_swap(w.begin() + i, w.begin() + i + 1); else if (i == e) rotate(w.begin(), w.begin() + 1, w.end()); else rotate(w.begin(), w.begin() + e, w.end()); int c_x = count_range(w.begin(), w.end()); int m_x = m + 1; if (c_x == target) { printf ("step: %d\n", m_x); return 0; } if (c_x > 0) { if (arr[c_x] == 0) { work.push_back(w); arr[c_x] = m + 1; } else if (arr[c_x] > m_x) { arr[c_x] = m_x; printf ("jiong~~~\n"); } } if (i < e) iter_swap(w.begin() + i, w.begin() + i + 1); else if (i == e) rotate(w.begin(), w.begin() + e, w.end()); else rotate(w.begin(), w.begin() + 1, w.end()); } } printf ("jiong ~~, can't find a path ????\n");}
[解决办法]