1.DFS(使用递归与回溯实现)
对于普通数组Array,这里给出函数模板形式:
#includeusing namespace std; template void func(T* arr, int total, int k = 0) //轮流更换第n位和n到total-1位 { for (int i = k; i < total; i++) { if (k == total - 1) //在此对排列好的数组进行下一步操作 { for (int p = 0; p < total; p++)cout << arr[p]; cout << "n"; return; } {T t = arr[i]; arr[i] = arr[k]; arr[k] = t; }//swap(a[k],a[i]); func(arr, total, k + 1); {T t = arr[i]; arr[i] = arr[k]; arr[k] = t; } } } int main() { int arr[]{ 1,2,3,4,5 }; func(arr, 5); char crr[] = "ABCDEFG"; func(crr, 4); return 0; }
对于字符串,则可跳过回溯步骤,相应地,空间复杂度将由O(1)提升至O( n! ),具体实现如下:
#includeusing namespace std; void f(string& str, int n = 0) { if (n == str.size() - 1)cout << str << endl; //在此对排列好的数组进行下一步操作 for (int i = n; i < str.size(); ++i) { string ts = str; auto t = ts[i]; ts[i] = ts[n]; ts[n] = t; f(ts, n + 1); } } int main() { return 0; string str = "1234567890"; f(str); return 0; }
2.调用 algorithm.h 中的next_permutation ()函数
伪代码如下:
do { // todo } while (next_permutation(a, a + n));
其中a为数组首地址,n为数组大小;
对于string或vector,在参数中传入首末迭代器即可。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)