Count different permutations after at most 2 swaps

Question

How do I solve the 2nd part of this problem if the input array may contain repeated numbers and the value of K = 2

Examples:

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 

My approach:
First, I count the different numbers in the array, then calculate an answer using DP (please see editorial of this problem).
Using those numbers, I tried some permutations, but the answer is incorrect.

I have already solve it with Time Complexity O(n^4),, is there any more efficient solution for this problem

Answer 1

Note: Code will be in Python, because it's easy. The logic should work for any language (more or less).

To reiterate the question:

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.

Let's address what we need to do:

• Make a collection of lists (I'll use a list of lists)
• Make some function that manipulates the list
• Find all results of swapping any two elements of all the original list
  • Repeat N-1 times for latest iterations of the original list

Now, I can address each "requirement", one at a time.

1. A list of lists
   • I like to set up my list variables that I'll test with later: D = [1,2,3,4], for example
   • master_list = []
2. My functions will be perm_count(orig_list, k) and permuter(my_list)
   • perm_count will be our "manager", adding elements to the list of lists
   • permuter will be doing our legwork, finding the swaps and returning them to perm_count
3. We'll use a loop to look through all the lists in the previous iteration and find all the swaps there-in. (you'll see in the code)
   • One thing to note is that, depending on the language, it's important to take a "snapshot" of the list with you start each "k" loop, or else the list will grow while you're working on it.
   • stuff it all in another loop and off we go!

Python code used in pythonfiddle.com

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)

Answer 2

Please don't answer now, Its question of ongoing contest.

[contest link][1]

https://www.codechef.com/MARCH16/problems/SEATSTR2