交换位置正确入座问题

Question

假设一共有八个座位，现在有编号分别为12345678的八个人坐在这八个座位上，每个人都有自己唯一的座位，初始状态未知，现在要求每个人找到自己的座位，每次只允许交换其中两个人的位置，每次交换后会提示目前已经正确位置的数目，该数由用户输入，求解最优交换方法，并将每次交换后的顺序打印出来（举个例子，先交换12位置，即目前位置为21345678，如果目前提示是1个位置正确，则在21345678中只有一个人位置正确，假设再交换34，则现在为21435678，提示3，则目前21435678中有3个位置正确，以此类推，直到8个位置全部正确，其中正确的数量由用户输入确定）

Answer 1

这个问题的本质就是最小编辑距离算法，也就是两个串最少变换几次得到另一个
你可以搜索下，如果还不会，我可以帮你写，给我评论即可。