相邻交换:逆序对给出最少次数

逻辑思维 · 建议年级 6

用逆序对变化与六种排列穷举证明321变123至少需要3次相邻交换。

下载视频
展开视频文字稿
  1. 数卡排成三、二、一,每次只能交换相邻两张。目标是排成一、二、三。
  2. 三二一里有三对顺序颠倒:三和二、三和一、二和一,所以至少需要消掉三个逆序。
  3. 第一次交换前两张,三二一变成二三一,只消掉三和二这一对。
  4. 第二次交换后两张,二三一变成二一三;第三次再交换前两张,得到一二三。
  5. 一次相邻交换最多减少一个逆序对,所以不可能少于三次;这条路线正好用了三次。
  6. 最少次数就是三。每次只交换相邻两张,并把交换前后的顺序写下来,就不容易漏步。
讲解依据

逻辑思维

逆序数下界与构造,并用反向检查确认。

看一个例子

数卡排成3、2、1,每次只能交换相邻两张。最少几次能变成1、2、3?

3次。列出三张卡的6种排列及相邻交换边,最短路径长度为3。

马上试一题

排列2、1、3最少几次相邻交换变1、2、3?