CODEWITHSUNDEEP
arraysalgorithmoptimization
Thel2oot
Thel2oot

Reputation: 21

How to find minimal swapping in two arrays

Given two positive integer arrays: A and B with same length. You can swapping elements between A and B.

Here is my problem.

Minimize total_number_of_swap(A,B)
subject to |sum(A)-sum(B)| ≤ delta

delta is a constant.

e.g.

A={4,2,3} , B={5,6,7} and delta=1

The one solution is total_number_of_swap(A,B)=1 (swap(A[2],B[2]))

A'={4,2,7}, B'={5,6,3}  

sum(A)=4+2+7=13, sum(B)=5+6+3=14 

|sum(A)-sum(B)| ≤ 1

How to find A' and B'.

Anybody have the algorithm to solve this problem? If you got, please tell me and I would be very grateful of you.

Upvotes: 2

Views: 108

Answers (1)

CoronA
CoronA

Reputation: 8075

This Problem is an extension to the Partition Problem. To solve it

  1. Put all numbers into one set and solve the Partition Problem (NP-Complete)
  2. Since you know the best solution from Step1, you know which element should belong to A and B. Swap those elements that are in the wrong set. (O(n) = Linear)

Upvotes: 1

Related Questions