SWAPS and cycle finding
SWAPS are used for insertion sorting algorithms. How to swap smartly? Let’s see some problems.
765. Couples Holding Hands
“Think about each couple as a vertex in the graph. So if there are N couples, there are N vertices. Now if in position 2i and 2i +1 there are person from couple u and couple v sitting there, that means that the permutations are going to involve u and v. So we add an edge to connect u and v. The min number of swaps = N — number of connected components. This follows directly from the theory of permutations. Any permutation can be decomposed into a composition of cyclic permutations. If the cyclic permutation involve k elements, we need k -1 swaps. You can think about each swap as reducing the size of the cyclic permutation by 1. So in the end, if the graph has k connected components, we need N — k swaps to reduce it back to N disjoint vertices.
Then there are many ways of doing this. We can use dfs for example to compute the number of connected components. The number of edges isn O(N). So this is an O(N) algorithm. We can also use union-find. I think a union-find is usually quite efficient. The following is an implementation.”
Cyclic findings can be used to solve this problem. Union find is used to solve this problem. Code is here.
class Solution(object):
def minSwapsCouples(self, row):
self.uf = {}
def union(x, y):
self.uf[find(y)] = find(x)
def find(x):
self.uf.setdefault(x, x)
if self.uf[x] !=x :
self.uf[x] = find(self.uf[x])
return self.uf[x]
N = len(row)//2
for i in range(N):
a, b = row[2*i], row[2*i+1]
union(a//2, b//2)
return len(row)-len({find(i) for i in range(2*N)})854. K-Similar Strings
BFS can be used to solve this problem.
class Solution:
def kSimilarity(self, A: str, B: str) -> int:
def graph(x: str) -> str:
i, xarr = 0, list(x)
while x[i] == B[i]:i += 1
# it means that xarr[i]!=B[i], we need find xarr[j]==B[i] and swap, at the same time, xarr[j] should not equal to B[j]
for j in range(i + 1, len(A)):
if xarr[j] == B[i] and xarr[j] != B[j]:
this_xarr = xarr[:]
this_xarr[i], this_xarr[j] = xarr[j], xarr[i]
yield ''.join(this_xarr)
def bfs():
Q, seen = collections.deque([(A, 0)]), {A}
while Q:
x, d = Q.popleft()
for y in graph(x):
if y not in seen:
if y == B:return d + 1
seen.add(y)
Q.append((y, d+1))
if A==B:return 0
return bfs()
