排列问题

好地方 · 发表于 2024-7-15 20:02:43

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

n个元素的序列，要求每次只能交换两个元素的位置，能否恰好用n!-1次交换，遍历序列的所有不同排列？如果可以，求算法。

aimisiyou · 发表于 2024-7-16 08:34:49

本帖最后由 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)
……
貌似递归冒泡可行。

KeyTo9_Fans · 发表于 2024-7-16 22:37:00

数学归纳法：

当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

lihpb00 · 发表于 2024-7-17 10:50:47

冒泡排序啊

账号		自动登录	找回密码
密码			欢迎注册

[求助] 排列问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。