Stable Roommates Check

Problem

Check whether a perfect matching of the stable roommates problem is stable.

prefs[i] is node i's preference list from most to least preferred and partner[i] is i's assigned partner. A blocking pair is two non-partners who each prefer the other over their assignment. Return False when any blocking pair exists.

Hint

Stability forbids any pair of non-partners who would rather be together.

Test cases

case 1

in: [[[1,2,3],[0,2,3],[1,0,3],[0,1,2]],[1,0,3,2]]

expected: true

case 2

in: [[[1,2,3],[0,2,3],[1,0,3],[0,1,2]],[2,3,0,1]]

expected: false

case 3

in: [[[1],[0]],[1,0]]

expected: true

Starter codePython

def stable_roommates_check(prefs, partner):
    # Your code here
    pass

3 test cases · run your code against them in the editor