fork download
  1. #!/usr/bin/python2.7
  2. """
  3. A majority ordering for 4 candidates A,B,C,D can be fully determined by 6 boolean values,
  4. characterizing the 6 pairwise comparisons: A vs B, A vs C, A vs D, B vs C, B vs D, C vs D.
  5.  
  6. (we only need booleans as with an odd number of voters, no equality is possible)
  7.  
  8. Hence, there are 2^6 = 64 possible orderings for 4 candidates.
  9.  
  10. For this simulation, lets represent each ordering as a vector of booleans:
  11. ordering = [compare(A,B), compare(A,C), compare(A,D), compare(B,C), compare(B,D), compare(C,D)]
  12.  
  13. Then, the transitive ordering A > C > B > D would be [1,1,1,0,1,1].
  14. """
  15.  
  16. CANDIDATES = frozenset(('A', 'B', 'C', 'D'))
  17. CANDIDATE_PAIR_TO_ORDERING_INDEX = {
  18. ('A', 'B') : 0,
  19. ('A', 'C') : 1,
  20. ('A', 'D') : 2,
  21. ('B', 'C') : 3,
  22. ('B', 'D') : 4,
  23. ('C', 'D') : 5,
  24. }
  25.  
  26. def ordering_to_string(ordering):
  27. comparisons = list(ordering)
  28. for candidates_pair, index in CANDIDATE_PAIR_TO_ORDERING_INDEX.iteritems():
  29. comparisons[index] = ('>' if ordering[index] else '<').join(candidates_pair)
  30. return ' ; '.join(comparisons)
  31.  
  32. def generate_all_orderings(vector_size):
  33. if vector_size == 0:
  34. yield []
  35. return
  36. for ordering in generate_all_orderings(vector_size - 1):
  37. yield [True] + ordering
  38. yield [False] + ordering
  39.  
  40. def is_ordering_intransitive(ordering):
  41. """
  42. An ordering is intransitive if we can find a cycle in it, starting from any candidate.
  43. This function uses a greedy method by trying all possible paths that could lead to a cycle.
  44. """
  45. for start_candidate in CANDIDATES:
  46. if find_cycle_in_ordering(ordering, current_candidate=start_candidate, candidates_checked=set()):
  47. return True
  48. return False
  49.  
  50. def find_cycle_in_ordering(ordering, current_candidate, candidates_checked):
  51. if current_candidate in candidates_checked:
  52. return True
  53. candidates_checked.add(current_candidate)
  54. for challenger_candidate in CANDIDATES:
  55. if challenger_candidate == current_candidate:
  56. continue
  57. if is_candidate_ranked_better(ordering, challenger_candidate, current_candidate):
  58. if find_cycle_in_ordering(ordering, challenger_candidate, candidates_checked.copy()): # recurse
  59. return True
  60. return False
  61.  
  62. def is_candidate_ranked_better(ordering, candidate1, candidate2):
  63. """Return True if candidate1 > candidate2 following the ordering"""
  64. # 'CANDIDATE_PAIR_TO_ORDERING_INDEX' only contains comparisons in one way, e.g. A vs B and not B vs A
  65. # Hence we need to reverse the logic in the later case
  66. if candidate1 < candidate2: # this is a nifty trick based on characters ordering
  67. return ordering[CANDIDATE_PAIR_TO_ORDERING_INDEX[(candidate1, candidate2)]]
  68. else:
  69. return not ordering[CANDIDATE_PAIR_TO_ORDERING_INDEX[(candidate2, candidate1)]]
  70.  
  71. if __name__ == '__main__':
  72. transitive_orderings = []
  73. intransitive_orderings = []
  74. for ordering in generate_all_orderings(vector_size=6):
  75. if is_ordering_intransitive(ordering):
  76. intransitive_orderings.append(ordering)
  77. else:
  78. transitive_orderings.append(ordering)
  79. print("There are {} transitive orderings:".format(len(transitive_orderings)))
  80. print('\n'.join(ordering_to_string(o) for o in transitive_orderings))
  81. print("There are {} intransitive orderings:".format(len(intransitive_orderings)))
  82. print('\n'.join(ordering_to_string(o) for o in intransitive_orderings))
  83.  
Success #stdin #stdout 0.01s 7852KB
stdin
Standard input is empty
stdout
There are 24 transitive orderings:
A>B ; A>C ; A>D ; B>C ; B>D ; C>D
A<B ; A>C ; A>D ; B>C ; B>D ; C>D
A<B ; A<C ; A>D ; B>C ; B>D ; C>D
A<B ; A<C ; A<D ; B>C ; B>D ; C>D
A>B ; A>C ; A>D ; B<C ; B>D ; C>D
A>B ; A<C ; A>D ; B<C ; B>D ; C>D
A<B ; A<C ; A>D ; B<C ; B>D ; C>D
A<B ; A<C ; A<D ; B<C ; B>D ; C>D
A>B ; A>C ; A>D ; B<C ; B<D ; C>D
A>B ; A<C ; A>D ; B<C ; B<D ; C>D
A>B ; A<C ; A<D ; B<C ; B<D ; C>D
A<B ; A<C ; A<D ; B<C ; B<D ; C>D
A>B ; A>C ; A>D ; B>C ; B>D ; C<D
A<B ; A>C ; A>D ; B>C ; B>D ; C<D
A<B ; A>C ; A<D ; B>C ; B>D ; C<D
A<B ; A<C ; A<D ; B>C ; B>D ; C<D
A>B ; A>C ; A>D ; B>C ; B<D ; C<D
A>B ; A>C ; A<D ; B>C ; B<D ; C<D
A<B ; A>C ; A<D ; B>C ; B<D ; C<D
A<B ; A<C ; A<D ; B>C ; B<D ; C<D
A>B ; A>C ; A>D ; B<C ; B<D ; C<D
A>B ; A>C ; A<D ; B<C ; B<D ; C<D
A>B ; A<C ; A<D ; B<C ; B<D ; C<D
A<B ; A<C ; A<D ; B<C ; B<D ; C<D
There are 40 intransitive orderings:
A>B ; A<C ; A>D ; B>C ; B>D ; C>D
A>B ; A>C ; A<D ; B>C ; B>D ; C>D
A<B ; A>C ; A<D ; B>C ; B>D ; C>D
A>B ; A<C ; A<D ; B>C ; B>D ; C>D
A<B ; A>C ; A>D ; B<C ; B>D ; C>D
A>B ; A>C ; A<D ; B<C ; B>D ; C>D
A<B ; A>C ; A<D ; B<C ; B>D ; C>D
A>B ; A<C ; A<D ; B<C ; B>D ; C>D
A>B ; A>C ; A>D ; B>C ; B<D ; C>D
A<B ; A>C ; A>D ; B>C ; B<D ; C>D
A>B ; A<C ; A>D ; B>C ; B<D ; C>D
A<B ; A<C ; A>D ; B>C ; B<D ; C>D
A>B ; A>C ; A<D ; B>C ; B<D ; C>D
A<B ; A>C ; A<D ; B>C ; B<D ; C>D
A>B ; A<C ; A<D ; B>C ; B<D ; C>D
A<B ; A<C ; A<D ; B>C ; B<D ; C>D
A<B ; A>C ; A>D ; B<C ; B<D ; C>D
A<B ; A<C ; A>D ; B<C ; B<D ; C>D
A>B ; A>C ; A<D ; B<C ; B<D ; C>D
A<B ; A>C ; A<D ; B<C ; B<D ; C>D
A>B ; A<C ; A>D ; B>C ; B>D ; C<D
A<B ; A<C ; A>D ; B>C ; B>D ; C<D
A>B ; A>C ; A<D ; B>C ; B>D ; C<D
A>B ; A<C ; A<D ; B>C ; B>D ; C<D
A>B ; A>C ; A>D ; B<C ; B>D ; C<D
A<B ; A>C ; A>D ; B<C ; B>D ; C<D
A>B ; A<C ; A>D ; B<C ; B>D ; C<D
A<B ; A<C ; A>D ; B<C ; B>D ; C<D
A>B ; A>C ; A<D ; B<C ; B>D ; C<D
A<B ; A>C ; A<D ; B<C ; B>D ; C<D
A>B ; A<C ; A<D ; B<C ; B>D ; C<D
A<B ; A<C ; A<D ; B<C ; B>D ; C<D
A<B ; A>C ; A>D ; B>C ; B<D ; C<D
A>B ; A<C ; A>D ; B>C ; B<D ; C<D
A<B ; A<C ; A>D ; B>C ; B<D ; C<D
A>B ; A<C ; A<D ; B>C ; B<D ; C<D
A<B ; A>C ; A>D ; B<C ; B<D ; C<D
A>B ; A<C ; A>D ; B<C ; B<D ; C<D
A<B ; A<C ; A>D ; B<C ; B<D ; C<D
A<B ; A>C ; A<D ; B<C ; B<D ; C<D