我正在研究一个整数序列,它没有相同的数字(不失一般性,让我们假设序列是一个排列1,2,...,n)到它的自然递增顺序(即1,2,...,n).我正在考虑直接交换元素(无论元素的位置如何;换句话说,交换对任何两个元素都有效),交换次数最少(以下可能是一个可行的解决方案):
交换两个元素的约束条件是应将其中一个或两个交换到正确的位置.直到每个元素都放在正确的位置.
但我不知道如何在数学上证明上述解决方案是否是最优的.有人可以帮忙吗？
我正在查看一个编程问题,当下面的问题突然变得相关时.
如何使用如下几个交换将字符串转换为另一个字符串.字符串保证是可互换的(它们具有相同的字符集,这是给出的),但字符可以重复.我在同一个问题上看到了网页结果,但没有重复字符.字符串中的任何两个字符都可以交换.
例如:"aabbccdd"可以在两次交换中转换为"ddbbccaa",并且"abcc"可以在一次交换中转换为"accb".
谢谢!