问动态编程:获得至少N个冒泡排序交换的方法有多少？
EN

Stack Overflow用户

提问于 2009-06-04 02:43:08

回答 1查看 3.2K关注 0票数 4

假设我有一个元素数组，它存在总排序。冒泡排序距离是在使用冒泡排序时对数组进行排序所需的交换次数。什么是一种有效的(可能涉及动态编程)方法来计算这个数组的可能排列的数量，它将具有小于或等于某个预先指定的数字的冒泡排序距离？

如果它简化了问题，您可以假设数组的所有元素都是唯一的(没有关联)。

发布于 2009-06-04 03:41:52

查看编辑距离的Wagner-Fisher algorithm。您可能正朝着相同的方向前进:使用允许您从左上角到右下角构建表的不变关系，构造一个包含最少交换的表，该表在您的问题中应该是n×n。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/948341

复制

相似问题

问动态编程:获得至少N个冒泡排序交换的方法有多少？EN