chkdup.py

#!/usr/bin/env python
# Weisi Dai <weisi@x-research.com>

t = 0

swaps = 0

def check(a, i):
    global swaps
    t = i
    if a[t] == t:
        return False
    while a[t] <> t:
        a[t], t = t, a[t]
        swaps = swaps + 1
    if t == i:
        return False
    return True

def checkDup(a):
    global swaps
    swaps = 0
    for i in range(len(a)):
        if check(a, i):
            return True
    return False

output_5

.....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
Salute! All answers correct! Max swaps = 5

test_chkdup.py

#!/usr/bin/env python
# Weisi Dai <weisi@x-research.com>

import chkdup
import sys

LENGTH = 5

def naive_checkDup(a):
    for x, itemx in enumerate(a):
        for y, itemy in enumerate(a[x + 1:]):
            if itemx == itemy:
                return True
    return False

def generate_arr(ID):
    ret = []
    for i in range(LENGTH):
        ret.append(ID % LENGTH)
        ID = ID / LENGTH
    return ret

wrong_ans = False
max_swaps = 0

for i in range(LENGTH ** LENGTH):
    arr = generate_arr(i)
    arr_copy = arr[:]

    ans_chkDup = chkdup.checkDup(arr)
    ans_naive_checkDup = naive_checkDup(arr_copy)

    max_swaps = max(max_swaps, chkdup.swaps)

    if ans_chkDup != ans_naive_checkDup:
        print "Wrong answer for %s" % arr_copy
        wrong_ans = True
    else:
        sys.stderr.write(".")

print
if wrong_ans:
    print "There's at least 1 wrong answer."
else:
    print "Salute! All answers correct! Max swaps = %s" % (max_swaps)

include

using namespace std;

template<typename Type, int SIZE>
bool swap_check(Type(&a)[SIZE], int index)
{
/* 获取此索引对应的元素值 */
int value = a[index];

/*  如果此索引等于其对应的值则直接返回true   */
if (index == value)
{
    return true;
}

/*  如果它的值作为索引而对应的值等于这个值则直接返回false   */
if (a[value] == value)
{
    return false;
}

/*  否则将此索引对应的元素和其元素值作为索引对应的元素交换    */
a[index] = a[value];
a[value] = value;

/*  然后再递归(检测)此索引   */
swap_check(a, index);

}
template<typename Type, int SIZE>
bool fuck(Type (&a)[SIZE])
{
for (int index = 0; index < SIZE; ++index)
{
/* 如果此索引对应的元素值不等于索引值，则尝试交换此元素 */
if (!swap_check(a, index))
{
return false;
}
}

return true;

}

int main()
{
int a[] = { 2, 3, 1, 0 , 6, 5, 4, 7};
bool ret = fuck(a);
return 0;
}