algorithm - 计算最多 2 次交换后的不同排列

Question

如何解决 this problem 的第二部分如果输入数组可能包含重复 数字和K = 2

的值

例子:

1 2 3 4     ans-18
1 2 3 4 5   ans-46
1 1 2 2 3   ans-26
1 1 1 2 2   ans-10
1 1 2 2 3 4 ans-56 

我的方法:
首先，我计算数组中的不同数字，然后使用 DP 计算答案(请参阅此问题的社论)。
使用这些数字，我尝试了一些排列，但答案不正确。

我已经用时间复杂度O(n^4)解决了，请问有没有更高效的解决办法

Answer 1

注意:代码将使用 Python，因为它很简单。该逻辑应该适用于任何语言(或多或少)。

重申一下这个问题:

You are given an array A = [1, 2, 3, ..., n]:
How many sequences (S2) can you get after at most k swaps on A?

An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1]. A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, i ≠ j.

让我们解决我们需要做的事情:

• 制作列表集合(我将使用列表列表)
• 编写一些操作列表的函数
• 查找所有原列表中任意两个元素交换的所有结果
  • 对原始列表的最新迭代重复 N-1 次

现在，我可以一次解决每个“需求”。

1. 列表列表
   • 我喜欢设置稍后测试的列表变量:D = [1,2,3,4]，例如
   • master_list = []
2. 我的函数将是 perm_count(orig_list, k) 和 permuter(my_list)
   • perm_count 将成为我们的“经理”，将元素添加到列表列表中
   • permuter 将完成我们的跑腿工作，找到交换并将它们返回给 perm_count
3. 我们将使用一个循环来查看上一次迭代中的所有列表，并找到其中的所有交换。 (你会在代码中看到)
   • 需要注意的一件事是，根据语言的不同，在开始每个“k”循环时拍摄列表的“快照”很重要，否则列表会在您处理它时增长。
   • 将其全部放入另一个循环中，然后我们开始吧!

pythonfiddle.com 中使用的 Python 代码

A = [1,2,3,4,5]  
B = [1,1,2,2,3]  
C = [1,2,3]  
D = [1,2,3,4]

def perm_count(orig_list, k):

master_list  = []
master_list.append(list(orig_list))
while k > 0:
    big_list = list(master_list) #"Snapshot" to ensure list-stability
    for each_list in big_list: #Looks at all the permutations from the previous "generations"
        for each_temp_list in permuter(each_list):
            if each_temp_list not in master_list:
                master_list.append(each_temp_list)
                #our masterlist now contains all the distinct lists from this run
                #If we run it again (the "k"), we get 2-swap combinations
                #and so on...

    k-=1

total_count = len(master_list)
print sorted(master_list) #If you need a sanity check, feel free to leave out
return total_count
#end perm_count

def permuter(my_list):#returns a list of lists
    lists_list = []
    #The below loop block returns all possible 1-swap combinations.
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            temp_list = my_list[:]
            if i != j:
                temp_list[i],temp_list[j] = temp_list[j],temp_list[i]
            if temp_list not in lists_list:
                lists_list.append(list(temp_list))

    return lists_list
#end permuter

print perm_count(B,2)