matching

matching.cpp

#include <cstdio>
#include <algorithm>

#define N 7
typedef char matching[N * 2];

/** @return negative if a is "better" than b. */
int compare(matching a, matching b)
{
    int vote = 0;
    for (int i = 0; i < N * 2; i++) {
        if (a[i] < b[i]) {
            vote--;
        } else if (a[i] > b[i]) {
            vote++;
        }
    }
    return vote;
}

bool beat_all_normal(matching m)
{
    matching normal;
    for (int shift = 0; shift < 2 * N; shift += 2) {
        // generate normal matching for each shift
        for (int i = 0; i < 2 * N; i++) {
            normal[i] = (i + shift) % (2 * N);
        }

        if (compare(m, normal) >= 0) return false;
    }

    return true;
}

int main()
{
    matching p;
    for (int i = 0; i < 2 * N; i++)
        p[i] = i;

    do {
        if (beat_all_normal(p)) {
            for (int i = 0; i < 2 * N; i++)
                printf("%d ", p[i]);
            puts("");
            // break;
        }
    } while (std::next_permutation(p, p + (N * 2)));

    return 0;
}