g****t
发帖数: 31659 | 1 假设有一组数A=[1,2,3,4,5]
它的另一个排列为B=[2,3,4,5,1]
显然，这样的不同数的排列A，B。可以通过两两交换从A走到B。
需要的步数和冒泡法排序一样。
现在我的问题是，假如排列中有相同的数，
那么需要多少次两两交换A可以变成B？
A=[1,2,2,2,5,6,8,9]
B=[1,9,8,2,5,6,2,2] | r****t
发帖数: 10904 | 2 冒泡法是稳定的，还是和冒泡法一样（如果两两交换限于相邻位置两两交换的话，前面
等同于冒泡就已经提供了相邻两两交换这个条件） | g****t
发帖数: 31659 | 3 A=[1,2,2,2,5,6,8,9]
B=[1,9,8,2,5,6,2,2]
从A到B，最少需要多少次交换，能算得出吗？
【在 r****t 的大作中提到】
: 冒泡法是稳定的，还是和冒泡法一样（如果两两交换限于相邻位置两两交换的话，前面
: 等同于冒泡就已经提供了相邻两两交换这个条件）
| g****t
发帖数: 31659 | 4 O，找到了。R里面有这个函数。我也是想用swap的次数当作距离。
https://rdrr.io/cran/CEGO/man/distancePermutationSwap.html
Schiavinotto, Tommaso, and Thomas Stuetzle. "A review of metrics on
permutations for search landscape analysis." Computers & operations research
34.10 (2007): 3143-3153.
【在 g****t 的大作中提到】
: A=[1,2,2,2,5,6,8,9]
: B=[1,9,8,2,5,6,2,2]
: 从A到B，最少需要多少次交换，能算得出吗？
| l*******m
发帖数: 1096 | 5 如果交换的距离也考虑，基本是lexicographical order， 直接用std::next_
permutation。
【在 g****t 的大作中提到】
: 假设有一组数A=[1,2,3,4,5]
: 它的另一个排列为B=[2,3,4,5,1]
: 显然，这样的不同数的排列A，B。可以通过两两交换从A走到B。
: 需要的步数和冒泡法排序一样。
: 现在我的问题是，假如排列中有相同的数，
: 那么需要多少次两两交换A可以变成B？
: A=[1,2,2,2,5,6,8,9]
: B=[1,9,8,2,5,6,2,2]
| g****t
发帖数: 31659 | 6 有重复字的时候。字母由低到高排序得到的次数。会不会不是
真正的最少swap数？
【在 l*******m 的大作中提到】
: 如果交换的距离也考虑，基本是lexicographical order， 直接用std::next_
: permutation。
| h*****2
发帖数: 2070 | 7
：
：假设有一组数A=[1,2,3,4,5]
有标准算法吧 | m*******n
发帖数: 305 | |
|
