#!/usr/bin/python2.7
"""
A majority ordering for 4 candidates A,B,C,D can be fully determined by 6 boolean values,
characterizing the 6 pairwise comparisons: A vs B, A vs C, A vs D, B vs C, B vs D, C vs D.
 
(we only need booleans as with an odd number of voters, no equality is possible)
 
Hence, there are 2^6 = 64 possible orderings for 4 candidates.
 
For this simulation, lets represent each ordering as a vector of booleans:
    ordering = [compare(A,B), compare(A,C), compare(A,D), compare(B,C), compare(B,D), compare(C,D)]
 
Then, the transitive ordering A > C > B > D would be [1,1,1,0,1,1].
"""
 
CANDIDATES = frozenset(('A', 'B', 'C', 'D'))
CANDIDATE_PAIR_TO_ORDERING_INDEX = {
        ('A', 'B') : 0,
        ('A', 'C') : 1,
        ('A', 'D') : 2,
        ('B', 'C') : 3,
        ('B', 'D') : 4,
        ('C', 'D') : 5,
}
 
def ordering_to_string(ordering):
    comparisons = list(ordering)
    for candidates_pair, index in CANDIDATE_PAIR_TO_ORDERING_INDEX.iteritems():
        comparisons[index] = ('>' if ordering[index] else '<').join(candidates_pair)
    return ' ; '.join(comparisons)
 
def generate_all_orderings(vector_size):
    if vector_size == 0:
        yield []
        return
    for ordering in generate_all_orderings(vector_size - 1):
        yield [True] + ordering
        yield [False] + ordering
 
def is_ordering_intransitive(ordering):
    """
    An ordering is intransitive if we can find a cycle in it, starting from any candidate.
    This function uses a greedy method by trying all possible paths that could lead to a cycle.
    """
    for start_candidate in CANDIDATES:
        if find_cycle_in_ordering(ordering, current_candidate=start_candidate, candidates_checked=set()):
            return True
    return False
 
def find_cycle_in_ordering(ordering, current_candidate, candidates_checked):
    if current_candidate in candidates_checked:
        return True
    candidates_checked.add(current_candidate)
    for challenger_candidate in CANDIDATES:
        if challenger_candidate == current_candidate:
            continue
        if is_candidate_ranked_better(ordering, challenger_candidate, current_candidate):
            if find_cycle_in_ordering(ordering, challenger_candidate, candidates_checked.copy()): # recurse
                return True
    return False
 
def is_candidate_ranked_better(ordering, candidate1, candidate2):
    """Return True if candidate1 > candidate2 following the ordering"""
    # 'CANDIDATE_PAIR_TO_ORDERING_INDEX' only contains comparisons in one way, e.g. A vs B and not B vs A
    # Hence we need to reverse the logic in the later case
    if candidate1 < candidate2: # this is a nifty trick based on characters ordering
        return ordering[CANDIDATE_PAIR_TO_ORDERING_INDEX[(candidate1, candidate2)]]
    else:
        return not ordering[CANDIDATE_PAIR_TO_ORDERING_INDEX[(candidate2, candidate1)]]
 
if __name__ == '__main__':
    transitive_orderings = []
    intransitive_orderings = []
    for ordering in generate_all_orderings(vector_size=6):
        if is_ordering_intransitive(ordering):
            intransitive_orderings.append(ordering)
        else:
            transitive_orderings.append(ordering)
    print("There are {} transitive orderings:".format(len(transitive_orderings)))
    print('\n'.join(ordering_to_string(o) for o in transitive_orderings))
    print("There are {} intransitive orderings:".format(len(intransitive_orderings)))
    print('\n'.join(ordering_to_string(o) for o in intransitive_orderings))
 

IyEvdXNyL2Jpbi9weXRob24yLjcKIiIiCkEgbWFqb3JpdHkgb3JkZXJpbmcgZm9yIDQgY2FuZGlkYXRlcyBBLEIsQyxEIGNhbiBiZSBmdWxseSBkZXRlcm1pbmVkIGJ5IDYgYm9vbGVhbiB2YWx1ZXMsCmNoYXJhY3Rlcml6aW5nIHRoZSA2IHBhaXJ3aXNlIGNvbXBhcmlzb25zOiBBIHZzIEIsIEEgdnMgQywgQSB2cyBELCBCIHZzIEMsIEIgdnMgRCwgQyB2cyBELgoKKHdlIG9ubHkgbmVlZCBib29sZWFucyBhcyB3aXRoIGFuIG9kZCBudW1iZXIgb2Ygdm90ZXJzLCBubyBlcXVhbGl0eSBpcyBwb3NzaWJsZSkKCkhlbmNlLCB0aGVyZSBhcmUgMl42ID0gNjQgcG9zc2libGUgb3JkZXJpbmdzIGZvciA0IGNhbmRpZGF0ZXMuCgpGb3IgdGhpcyBzaW11bGF0aW9uLCBsZXRzIHJlcHJlc2VudCBlYWNoIG9yZGVyaW5nIGFzIGEgdmVjdG9yIG9mIGJvb2xlYW5zOgogICAgb3JkZXJpbmcgPSBbY29tcGFyZShBLEIpLCBjb21wYXJlKEEsQyksIGNvbXBhcmUoQSxEKSwgY29tcGFyZShCLEMpLCBjb21wYXJlKEIsRCksIGNvbXBhcmUoQyxEKV0KClRoZW4sIHRoZSB0cmFuc2l0aXZlIG9yZGVyaW5nIEEgPiBDID4gQiA+IEQgd291bGQgYmUgWzEsMSwxLDAsMSwxXS4KIiIiCgpDQU5ESURBVEVTID0gZnJvemVuc2V0KCgnQScsICdCJywgJ0MnLCAnRCcpKQpDQU5ESURBVEVfUEFJUl9UT19PUkRFUklOR19JTkRFWCA9IHsKICAgICAgICAoJ0EnLCAnQicpIDogMCwKICAgICAgICAoJ0EnLCAnQycpIDogMSwKICAgICAgICAoJ0EnLCAnRCcpIDogMiwKICAgICAgICAoJ0InLCAnQycpIDogMywKICAgICAgICAoJ0InLCAnRCcpIDogNCwKICAgICAgICAoJ0MnLCAnRCcpIDogNSwKfQoKZGVmIG9yZGVyaW5nX3RvX3N0cmluZyhvcmRlcmluZyk6CiAgICBjb21wYXJpc29ucyA9IGxpc3Qob3JkZXJpbmcpCiAgICBmb3IgY2FuZGlkYXRlc19wYWlyLCBpbmRleCBpbiBDQU5ESURBVEVfUEFJUl9UT19PUkRFUklOR19JTkRFWC5pdGVyaXRlbXMoKToKICAgICAgICBjb21wYXJpc29uc1tpbmRleF0gPSAoJz4nIGlmIG9yZGVyaW5nW2luZGV4XSBlbHNlICc8Jykuam9pbihjYW5kaWRhdGVzX3BhaXIpCiAgICByZXR1cm4gJyA7ICcuam9pbihjb21wYXJpc29ucykKCmRlZiBnZW5lcmF0ZV9hbGxfb3JkZXJpbmdzKHZlY3Rvcl9zaXplKToKICAgIGlmIHZlY3Rvcl9zaXplID09IDA6CiAgICAgICAgeWllbGQgW10KICAgICAgICByZXR1cm4KICAgIGZvciBvcmRlcmluZyBpbiBnZW5lcmF0ZV9hbGxfb3JkZXJpbmdzKHZlY3Rvcl9zaXplIC0gMSk6CiAgICAgICAgeWllbGQgW1RydWVdICsgb3JkZXJpbmcKICAgICAgICB5aWVsZCBbRmFsc2VdICsgb3JkZXJpbmcKCmRlZiBpc19vcmRlcmluZ19pbnRyYW5zaXRpdmUob3JkZXJpbmcpOgogICAgIiIiCiAgICBBbiBvcmRlcmluZyBpcyBpbnRyYW5zaXRpdmUgaWYgd2UgY2FuIGZpbmQgYSBjeWNsZSBpbiBpdCwgc3RhcnRpbmcgZnJvbSBhbnkgY2FuZGlkYXRlLgogICAgVGhpcyBmdW5jdGlvbiB1c2VzIGEgZ3JlZWR5IG1ldGhvZCBieSB0cnlpbmcgYWxsIHBvc3NpYmxlIHBhdGhzIHRoYXQgY291bGQgbGVhZCB0byBhIGN5Y2xlLgogICAgIiIiCiAgICBmb3Igc3RhcnRfY2FuZGlkYXRlIGluIENBTkRJREFURVM6CiAgICAgICAgaWYgZmluZF9jeWNsZV9pbl9vcmRlcmluZyhvcmRlcmluZywgY3VycmVudF9jYW5kaWRhdGU9c3RhcnRfY2FuZGlkYXRlLCBjYW5kaWRhdGVzX2NoZWNrZWQ9c2V0KCkpOgogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgcmV0dXJuIEZhbHNlCgpkZWYgZmluZF9jeWNsZV9pbl9vcmRlcmluZyhvcmRlcmluZywgY3VycmVudF9jYW5kaWRhdGUsIGNhbmRpZGF0ZXNfY2hlY2tlZCk6CiAgICBpZiBjdXJyZW50X2NhbmRpZGF0ZSBpbiBjYW5kaWRhdGVzX2NoZWNrZWQ6CiAgICAgICAgcmV0dXJuIFRydWUKICAgIGNhbmRpZGF0ZXNfY2hlY2tlZC5hZGQoY3VycmVudF9jYW5kaWRhdGUpCiAgICBmb3IgY2hhbGxlbmdlcl9jYW5kaWRhdGUgaW4gQ0FORElEQVRFUzoKICAgICAgICBpZiBjaGFsbGVuZ2VyX2NhbmRpZGF0ZSA9PSBjdXJyZW50X2NhbmRpZGF0ZToKICAgICAgICAgICAgY29udGludWUKICAgICAgICBpZiBpc19jYW5kaWRhdGVfcmFua2VkX2JldHRlcihvcmRlcmluZywgY2hhbGxlbmdlcl9jYW5kaWRhdGUsIGN1cnJlbnRfY2FuZGlkYXRlKToKICAgICAgICAgICAgaWYgZmluZF9jeWNsZV9pbl9vcmRlcmluZyhvcmRlcmluZywgY2hhbGxlbmdlcl9jYW5kaWRhdGUsIGNhbmRpZGF0ZXNfY2hlY2tlZC5jb3B5KCkpOiAjIHJlY3Vyc2UKICAgICAgICAgICAgICAgIHJldHVybiBUcnVlCiAgICByZXR1cm4gRmFsc2UKCmRlZiBpc19jYW5kaWRhdGVfcmFua2VkX2JldHRlcihvcmRlcmluZywgY2FuZGlkYXRlMSwgY2FuZGlkYXRlMik6CiAgICAiIiJSZXR1cm4gVHJ1ZSBpZiBjYW5kaWRhdGUxID4gY2FuZGlkYXRlMiBmb2xsb3dpbmcgdGhlIG9yZGVyaW5nIiIiCiAgICAjICdDQU5ESURBVEVfUEFJUl9UT19PUkRFUklOR19JTkRFWCcgb25seSBjb250YWlucyBjb21wYXJpc29ucyBpbiBvbmUgd2F5LCBlLmcuIEEgdnMgQiBhbmQgbm90IEIgdnMgQQogICAgIyBIZW5jZSB3ZSBuZWVkIHRvIHJldmVyc2UgdGhlIGxvZ2ljIGluIHRoZSBsYXRlciBjYXNlCiAgICBpZiBjYW5kaWRhdGUxIDwgY2FuZGlkYXRlMjogIyB0aGlzIGlzIGEgbmlmdHkgdHJpY2sgYmFzZWQgb24gY2hhcmFjdGVycyBvcmRlcmluZwogICAgICAgIHJldHVybiBvcmRlcmluZ1tDQU5ESURBVEVfUEFJUl9UT19PUkRFUklOR19JTkRFWFsoY2FuZGlkYXRlMSwgY2FuZGlkYXRlMildXQogICAgZWxzZToKICAgICAgICByZXR1cm4gbm90IG9yZGVyaW5nW0NBTkRJREFURV9QQUlSX1RPX09SREVSSU5HX0lOREVYWyhjYW5kaWRhdGUyLCBjYW5kaWRhdGUxKV1dCgppZiBfX25hbWVfXyA9PSAnX19tYWluX18nOgogICAgdHJhbnNpdGl2ZV9vcmRlcmluZ3MgPSBbXQogICAgaW50cmFuc2l0aXZlX29yZGVyaW5ncyA9IFtdCiAgICBmb3Igb3JkZXJpbmcgaW4gZ2VuZXJhdGVfYWxsX29yZGVyaW5ncyh2ZWN0b3Jfc2l6ZT02KToKICAgICAgICBpZiBpc19vcmRlcmluZ19pbnRyYW5zaXRpdmUob3JkZXJpbmcpOgogICAgICAgICAgICBpbnRyYW5zaXRpdmVfb3JkZXJpbmdzLmFwcGVuZChvcmRlcmluZykKICAgICAgICBlbHNlOgogICAgICAgICAgICB0cmFuc2l0aXZlX29yZGVyaW5ncy5hcHBlbmQob3JkZXJpbmcpCiAgICBwcmludCgiVGhlcmUgYXJlIHt9IHRyYW5zaXRpdmUgb3JkZXJpbmdzOiIuZm9ybWF0KGxlbih0cmFuc2l0aXZlX29yZGVyaW5ncykpKQogICAgcHJpbnQoJ1xuJy5qb2luKG9yZGVyaW5nX3RvX3N0cmluZyhvKSBmb3IgbyBpbiB0cmFuc2l0aXZlX29yZGVyaW5ncykpCiAgICBwcmludCgiVGhlcmUgYXJlIHt9IGludHJhbnNpdGl2ZSBvcmRlcmluZ3M6Ii5mb3JtYXQobGVuKGludHJhbnNpdGl2ZV9vcmRlcmluZ3MpKSkKICAgIHByaW50KCdcbicuam9pbihvcmRlcmluZ190b19zdHJpbmcobykgZm9yIG8gaW4gaW50cmFuc2l0aXZlX29yZGVyaW5ncykpCg==