Hello everybody. Recently, I was thinking about a one problem and now I want to share it with you:

You have two arrays of the same length n, and you have to calculate minimum number of swaps of two arbitrary indexes which transform the first array A into the second B. ( All elements in arrays are not neccessery distinct ) I know how to solve this problem when all elements are distinct in O(n). Do you know how to solve common problem in effective asymptotics?

Thank you in advance!

Check out this problem from AtCoder. It's quite possible that you can use a very similar approach (and the answer will be slightly smaller as you can swap arbitrary elements).

If all elements are distinct then solution is with dfs (cycle counting), am I right?

Yes

i know o(nlogn) solution by sorting and using fenwick tree, no matter if elements distinct or not ?

may you explain your o(n) solution for the problem if all elements is different ?

Here check my code for finding minimum swaps to sort (I think it is understandable from code, if you didn't get, write):

he didn't ask for converting the first array to a sorted array.

he asks that he will give you two different arrays, and you want to convert the first one to the second in minimum number of swaps.

like 1 6 3 4 2 to 6 3 1 2 4

ans will be 3

is there o(n) solution for that !

These problems are almost same, just fix array B to {1, 2, 3, ..,

n}i think there are not the same,

and by the way, i tested your solution for 3 2 5 1 4 and it output 2, what that means, is it required 2 swaps to sort the element ? how ?

almost same ≠ fully sameCheck code below

Btw, my code prints 3 for your array...

Here I just edited code for 2 arrays :)

CodeCan we count the inversions of a permutation on N numbers in O(N) complexity?

No

Would you please elaborate that technique to me or share some links? ( I am TooNewbie :) )

Let's build directed graph G = (V, E). V ={a[i] | i = 1 .. n}. E = {(b_i, a_i) | i = 1 .. n}. Now we have to cover this graph with maximal number of edge-disjoint cycles.

Also we can generate arrays for each graph with income degrees equals to outcome degrees.

I think that this problem is NP-hard. But I would happy to know solution if I am not correct.

I couldn't found appropriate article. But for example here http://www.math.ucsd.edu/~jverstra/cycle2.pdf in Introduction is information that problem of packing maximal count of edge-disjoint cycles in graph (both directed and undirected) is NP-hard. I think that our problem is similar.

Yea, I think you can do a reduction from the problem you linked. Let's make a distinction:

Maximal cycle packing: Find a maximal number of simple edge-disjoint cycles in (V,A), not necessarily covering all arcs. Link claims this isNP-Complete*.Maximal cycle cover: Find a maximal number of simple edge-disjoint cycles in (V,A), such that each edge is covered by a cycle. We want to prove this isNP-Complete.Lemma 1: a graph has a cycle cover if and only if

indeg(v) =outdeg(v) for allv(trivial)Suppose we can solve the maximal cycle cover problem efficiently. Given a digraph (

V,A) to solve the maximal cycle packing problem on, we add one extra vertexu', and for every , ifindeg(v) >outdeg(v) we addindeg(v) -outdeg(v) arcs** fromvtou', and vice versa if the inequality reverses. This gives us a new digraph (V',A'). Note: clearlyindeg(v) =outdeg(v) for allv(includingu') in the end, so (V',A') has a cycle cover.Now suppose that you have an optimal cycle packing on (

V,A) withksimple cycles, then you can extend this to a solution for the cycle cover problem on (V',A') withk+indeg(u'): first we remove all these cycles from (V',A') (recall that (V,A) is contained in (V',A')). This doesn't change that fact thatindeg(v) =outdeg(v) for allv, so the resultant graph still has a cycle cover. In addition, there are no cycles thatdon'tpass throughu' (otherwise, we could add this cycle to our packing for (V,A)). Thus, after removing the cycle packing on (V,A) from (V',A'), we can decompose the remains of the graph into exactlyindeg(u') simple cycles (quickly, using e.g. Hierholzers algorithm). So we proved:Thm 1: A optimal packing of

kcycles in (V,A) gives rise to a cover ofk+indeg(u') cycles in (V',A').Conversely, suppose we have an optimal cover of

k' simple cycles over (V',A'), then there must be exactlyindeg(u') simple cycles going throughu' (_exactly_indeg(u') since this is a cover). Remove these cycles, and you end up with a cycle packing withk' -indeg(u') simple cycles in (V,A). Thus:Thm 2: An optimal cover of

k' cycles in (V',A') gives rise to a packing ofk' -indeg(u') cycles in (V,A).This clearly implies that the optimal solution to the cycle packing problem on (

V,A) differs from the cycle cover problem on (V',A') byindeg(u') (a constant that depends only on (V,A)), and that we can efficiently reconstruct such a packing, given an optimal cover. Thus, the cycle cover problem is alsoNP-Complete.*: The linked paper claims it is

NP-Complete but doesn't provide a proof. I can't find any either (other than two more papers making the claim without a proof or citation).**: Not sure if we're allowing multi-edges, but clearly you can replace

kcopies of (u,v) with (u,w_{i}) and (w_{i},v) forknew verticesw_{i}, without really affecting the problem.