请教一个离散数学问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

请教一个离散数学问题

请教一个离散数学问题# Programming - 葵花宝典

g*t2019-02-06 08:02

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*t2019-02-06 08:02

2 楼

冒泡法是稳定的，还是和冒泡法一样（如果两两交换限于相邻位置两两交换的话，前面
等同于冒泡就已经提供了相邻两两交换这个条件）

g*t2019-02-06 08:02

3 楼

A=[1,2,2,2,5,6,8,9]
B=[1,9,8,2,5,6,2,2]
从A到B，最少需要多少次交换，能算得出吗？

【在 r****t 的大作中提到】

: 冒泡法是稳定的，还是和冒泡法一样（如果两两交换限于相邻位置两两交换的话，前面
: 等同于冒泡就已经提供了相邻两两交换这个条件）

g*t2019-02-06 08:02

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*m2019-02-06 08:02

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*t2019-02-06 08:02

6 楼

有重复字的时候。字母由低到高排序得到的次数。会不会不是
真正的最少swap数？

【在 l*******m 的大作中提到】

: 如果交换的距离也考虑，基本是lexicographical order，直接用std::next_
: permutation。