algorithm - 计算序列数

Question

问题是:
给定一个正整数序列 A={1,2,3,...,N}。
计算你能得到的序列个数 K 给定 N 的相邻交换>?
我的做法:
我解决此类编程问题的算法非常幼稚。我只能想到进行所有可能的 k 交换，然后计算序列。
谁能帮我找出更好的算法？

Answer 1

反转

这类问题(交换相邻元素)的关键是考虑每次交换后排列中的反转次数。

如果 a[i] > a[j] 且 i < j，则两个元素 a[i] 和 a[j] 形成一个反转。

排列中的反转数是形成反转的元素对的数量。

之所以有用，是因为无论何时执行相邻元素的交换，反转计数都会增加 1 或减少 1。

解决问题的提示

因此，K次交换后的总反转次数必须为以下值之一:K，K-2，K-4等。

因此，我们已将问题简化为使用 K 或 K-2 或 K-4 等反转来计算排列的数量。 triangle of Mahonian numbers 给出了具有给定反转次数的排列数.

解决问题的代码

您需要做的就是计算三角形的第 N 行(代码可以在 here 中找到)，然后对相应的条目求和:

row = mahonian_row(N)
print sum(row[n] for n in range(K+1) if n%2==K%2 and n<len(row))