# Task
 Sorting is one of the most basic computational devices used in Computer Science. 
 
 Given a sequence (length ≤ 1000) of 3 different key values (7, 8, 9), your task is to find the minimum number of exchange operations necessary to make the sequence sorted. 

 One operation is the switching of 2 key values in the sequence.

# Example

 For `sequence = [7, 7, 8, 8, 9, 9]`, the result should be `0`.
 
 It's already a sorted sequence.

 For `sequence = [9, 7, 8, 8, 9, 7]`, the result should be `1`.
 
 We can switching `sequence[0]` and `sequence[5]`.
 
 For `sequence = [8, 8, 7, 9, 9, 9, 8, 9, 7]`, the result should be `4`.
 
 We can:
```
 [8, 8, 7, 9, 9, 9, 8, 9, 7] 
 switching sequence[0] and sequence[3]
 --> [9, 8, 7, 8, 9, 9, 8, 9, 7]
 switching sequence[0] and sequence[8]
 --> [7, 8, 7, 8, 9, 9, 8, 9, 9]
 switching sequence[1] and sequence[2]
 --> [7, 7, 8, 8, 9, 9, 8, 9, 9]
 switching sequence[5] and sequence[7]
 --> [7, 7, 8, 8, 8, 9, 9, 9, 9] 
```
So `4` is the minimum number of operations for the sequence to become sorted.

# Input/Output


 - `[input]` integer array `sequence`

  The Sequence.


 - `[output]` an integer

  the minimum number of operations.

Difficulty: interview

Starter code:

def exchange_sort(sequence):
	

Solutions:
from collections import Counter

def exchange_sort(sequence):
    """Greedy algorithm based on permutation cycle decomposition:
    1. Search for transposition placing TWO elements correctly.
    2. Search iteratively for transposition placing ONE elements correctly."""
    swaps, cnt = 0, Counter()
    for a, b in zip(sequence, sorted(sequence)):
        if cnt[b,a] > 0:
            cnt[b,a] -= 1
            swaps += 1
        elif a != b:
            cnt[a,b] += 1
    # Special case: as there are only three keys at most,
    # all remaining cycles will be 3-length cycles that
    # need 2 transpositions to place 3 elements correctly.
    return swaps + sum(cnt.values()) // 3 * 2

from collections import Counter

def exchange_sort(s):
    a,b,c = (Counter(zip(*p)) for p in ((s,sorted(s)), (sorted(s),s), (s,s)))
    return sum(((a|b) + a + b - c - c - c).values()) // 6

def exchange_sort(l):
    a,b,c = l.count(7),-l.count(9),-l.count(8)
    if b!=0: return (a - l[:a].count(7) + max(l[a:b].count(9), l[b:].count(8))) 
    t=sorted(l)
    r=0
    for i in range(len(l)): r+=1 if t[i]>l[i] else 0
    return r

from collections import Counter

def exchange_sort(sequence):
    a, b, c = map(Counter(sequence).get, (7, 8, 9))
    if not (a and b and c): return sum(x < y for x,y in zip(sorted(sequence), sequence))
    return sequence[a:].count(7) + max(sequence[-c:].count(8), sequence[a:-c].count(9))

def exchange_sort(xs):
    xs7, xs9 = xs[:xs.count(7)], xs[len(xs)-xs.count(9):]
    return xs7.count(8) + xs9.count(8) + max(xs7.count(9), xs9.count(7))

def exchange_sort(s):
    t7, t8 = s.count(7), s.count(8)
    n97, n79 = s[:t7].count(9), s[t7 + t8:].count(7)
    n87, n98 = s[:t7].count(8), s[t7:t7 + t8].count(9)
    return 2 * n97 + n87 + n98 - min(n79, n97)    


def lsorter2(l):
    intsec = [(a,b) for (a,b) in zip(l, sorted(l)) if a!=b]
    return list(zip(*intsec))

def naturalSwap(l):
    x1 = lsorter2(l)
    ori = list(x1[0])
    sort = list(x1[1])

    si = [i for i, x in enumerate(sort) if x == ori[0]]
    fi = [i for i, x in enumerate(ori) if x == sort[0]]

    ci = [x for x in si if x in fi]

    new_ori = [x for i,x in enumerate(ori) if i not in ci]

    swap_num1 = len(ci)

    si2 = [i for i, x in enumerate(ori) if x == ori[0]]
    fi2 = [i for i, x in enumerate(sort) if x == sort[0]]

    ci2 = [x for x in si2 if x in fi2]

    new_ori2 = [x for i,x in enumerate(ori) if i not in ci2]

    swap_num2 = len(ci2)

    swap_real= min(swap_num1,swap_num2)

    to_force_swap1 = ci[:swap_real]
    to_force_swap2 = ci2[:swap_real]

    to_force_swap3 = to_force_swap1 + to_force_swap2

    new_list = [x for i, x in enumerate(ori) if i not in to_force_swap3]
    return (new_list, swap_real)

def forcedSwap(l):
    x1 = lsorter2(l)
    ori = list(x1[0])
    sort = list(x1[1])

    idx = ori.index(sort[0])
    ori[0], ori[idx] = ori[idx], ori[0]
    return ori



def exchange_sort(l):
    swaps = 0
    dlist = l[:]
    cnt = 1
    if dlist == sorted(dlist):
        return 0
    
    else:
        while cnt > 0 and len(dlist) > 0:
            cnt = 0
            x1 = naturalSwap(dlist)
            cnt = x1[1]
            swaps += x1[1]
            dlist = x1[0]
        while len(dlist) > 2:
            x2 = forcedSwap(dlist)
            swaps+=1
            dlist = x2
        return swaps


from collections import defaultdict, Counter

# the special case allows for linear solution
def exchange_sort(sequence):
    n_sevens, n_eights = sequence.count(7), sequence.count(8)
    sevens = defaultdict(lambda: 0, Counter(sequence[:n_sevens]))
    eights = defaultdict(lambda: 0, Counter(sequence[n_sevens:n_sevens + n_eights]))
    nines = defaultdict(lambda: 0, Counter(sequence[n_sevens + n_eights:]))
    direct_78 = min(sevens[8], eights[7])
    direct_79 = min(sevens[9], nines[7])
    direct_89 = min(eights[9], nines[8])
    sevens[8] -= direct_78
    nines[7] -= direct_79
    nines[8] -= direct_89
    eights[7] -= direct_78
    eights[9] -= direct_89
    sevens[7], eights[8], nines[9] = 0, 0, 0
    return direct_78 + direct_79 + direct_89 + sum(nines.values()) * 2

def exchange_sort(sequence):
    a=sequence[:]
    seven=a.count(7)
    eight=a.count(8)
    r=0
    for i in range(seven,len(a)):
        if a[i]==7:
            r+=1
            if i<seven+eight and 8 in a[:seven]:
                j=a.index(8)
            else:              
                for j in range(seven):
                    if a[j]!=7:
                        break
            a[i],a[j]=a[j],a[i]
    r+=a[seven+eight:].count(8)
    return r

def exchange_sort(sequence):
    print(sequence)
    # Reduce the sequence into its useful data
    counts = [sequence.count(n) for n in [7, 8, 9]]
    dividers = [0] + [sum(counts[:i]) for i in range(1,4)]
    groupings = [[sequence[dividers[i]:dividers[i+1]].count(n) for n in [7, 8, 9]] for i in range(3)]
    # Perform swaps en masse until done
    n = 0
    def swap(t0, t1, n0, n1):
        swappable = min(groupings[t0][n1], groupings[t1][n0])
        groupings[t0][n0] += swappable
        groupings[t0][n1] -= swappable
        groupings[t1][n1] += swappable
        groupings[t1][n0] -= swappable
        return swappable
    for a, b in [(0, 1), (0, 2), (1, 2)]:
        n += swap(a, b, a, b)
    for a, b, c in [(0, 1, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0), (1, 0, 2), (0, 2, 1)]:
        n += swap(a, b, a, c)
    for a, b in [(0, 1), (0, 2), (1, 2)]:
        n += swap(a, b, a, b)
    return n