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 | |
|