排列问题
n个元素的序列，要求每次只能交换两个元素的位置，能否恰好用n!-1次交换，遍历序列的所有不同排列？如果可以，求算法。 本帖最后由 aimisiyou 于 2024-7-16 08:36 编辑当n=2时：(1,2）->(2,1)
当n=3时：(1,2,3)->(1,3,2)->(2,3,1)->(2,1,3)->(3,1,2)->(3,2,1)
……
貌似递归冒泡可行。 数学归纳法：
当n=2时，显然可行
假设当n=k时可行，那么当n=k+1时，方案如下：
第1个元素“1”不动，用n=k的换法把第2到第(k+1)个元素交换一遍
把“2”换到第1个位置，用n=k的换法把第2到第(k+1)个元素交换一遍
把“3”换到第1个位置，用n=k的换法把第2到第(k+1)个元素交换一遍
……
把“k+1”换到第1个位置，用n=k的换法把第2到第(k+1)个元素交换一遍
所以无论n是几，都是可行的
例如：当n=4时，换法如下：
第1个元素“1”不动，用n=3的换法把第2到第(k+1)个元素交换一遍：
1234 1243 1342 1324 1423 1432
把“2”换到第1个位置，用n=3的换法把第2到第(k+1)个元素交换一遍：
2431 2413 2314 2341 2143 2134
把“3”换到第1个位置，用n=3的换法把第2到第(k+1)个元素交换一遍：
3124 3142 3241 3214 3412 3421
把“4”换到第1个位置，用n=3的换法把第2到第(k+1)个元素交换一遍：
4321 4312 4213 4231 4132 4123 冒泡排序啊
页:
[1]