由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 请教一个离散数学问题
相关主题
FP的教材是怎么误导人的另一个相关的很基础的问题
怎么产生全排列?问一个关于convex set的数学问题 (转载)
谁给一个recursive的string permutation的c code吧基础不行,怎么办
permutation in a loop谁提示一下
metric 不参与DL的具体优化吧?[合集] 快慢指针找链表中的环,别的步长行么?
CS相关经典书籍的书评[转载][合集] 关于求解链表中环的起始位置问题
来,做题吧。[合集] goog code jam俺水掉了。
问个算法问题对纯粹的算法感兴趣 哪里有资源
相关话题的讨论汇总
话题: 交换话题: 两两话题: 离散数学话题: 排列话题: 多少次
进入Programming版参与讨论
1 (共1页)
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
1 (共1页)
进入Programming版参与讨论
相关主题
又一个算法题metric 不参与DL的具体优化吧?
10个数所有的组对可能, 怎么解?CS相关经典书籍的书评[转载]
请教VB的条件判断语句来,做题吧。
请教一个关于循环的问题问个算法问题
FP的教材是怎么误导人的另一个相关的很基础的问题
怎么产生全排列?问一个关于convex set的数学问题 (转载)
谁给一个recursive的string permutation的c code吧基础不行,怎么办
permutation in a loop谁提示一下
相关话题的讨论汇总
话题: 交换话题: 两两话题: 离散数学话题: 排列话题: 多少次