How to resolve the algorithm Stable marriage problem step by step in the BBC BASIC programming language

Published on 12 May 2024 09:40 PM
#Bbc basic

How to resolve the algorithm Stable marriage problem step by step in the BBC BASIC programming language

Table of Contents

Problem Statement

Solve the Stable marriage problem using the Gale/Shapley algorithm.

Problem description Given an equal number of men and women to be paired for marriage, each man ranks all the women in order of his preference and each woman ranks all the men in order of her preference. A stable set of engagements for marriage is one where no man prefers a woman over the one he is engaged to, where that other woman also prefers that man over the one she is engaged to. I.e. with consulting marriages, there would be no reason for the engagements between the people to change. Gale and Shapley proved that there is a stable set of engagements for any set of preferences and the first link above gives their algorithm for finding a set of stable engagements.

Task Specifics Given ten males: And ten females: And a complete list of ranked preferences, where the most liked is to the left:

References

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Stable marriage problem step by step in the BBC BASIC programming language

Source code in the bbc programming language

      N = 10
      DIM mname$(N), wname$(N), mpref$(N), wpref$(N), mpartner%(N), wpartner%(N)
      DIM proposed&(N,N)
      mname$() = "", "Abe","Bob","Col","Dan","Ed","Fred","Gav","Hal","Ian","Jon"
      wname$() = "", "Abi","Bea","Cath","Dee","Eve","Fay","Gay","Hope","Ivy","Jan"
      mpref$() = "", "AECIJDFBHG","CHADEFBJIG","HEADBFIGCJ","IFDGHEJBCA","JDBCFEAIHG",\
      \              "BADGEICJHF","GEIBCADHJF","AEHFICJBGD","HCDGBAFIJE","AFJGEBDCIH"
      wpref$() = "", "BFJGIADECH","BACFGDIEJH","FBEGHCIADJ","FJCAIHGDBE","JHFDAGCEIB",\
      \              "BAEIJDFGCH","JGHFBACEDI","GJBAIDHECF","ICHGFBAEJD","EHGABJCIFD"
      
      REM The Gale-Shapley algorithm:
      REPEAT
        FOR m% = 1 TO N
          REPEAT
            IF mpartner%(m%) EXIT REPEAT
            FOR i% = 1 TO N
              w% = ASCMID$(mpref$(m%),i%) - 64
              IF proposed&(m%,w%) = 0 EXIT FOR
            NEXT i%
            IF i% > N EXIT REPEAT
            proposed&(m%,w%) = 1
            IF wpartner%(w%) = 0 THEN
              mpartner%(m%) = w% : REM Get engaged
              wpartner%(w%) = m%
            ELSE
              o% = wpartner%(w%)
              IF INSTR(wpref$(w%), LEFT$(mname$(m%),1)) < \
              \  INSTR(wpref$(w%), LEFT$(mname$(o%),1)) THEN
                mpartner%(o%) = 0  : REM Split up
                mpartner%(m%) = w% : REM Get engaged
                wpartner%(w%) = m%
              ENDIF
            ENDIF
          UNTIL TRUE
        NEXT m%
      UNTIL SUM(mpartner%()) = (N*(N+1))/2
      
      FOR m% = 1 TO N
        PRINT mname$(m%) " is engaged to " wname$(mpartner%(m%))
      NEXT
      PRINT "Relationships are ";
      IF FNstable PRINT "stable." ELSE PRINT "unstable."
      
      a% = RND(N)
      REPEAT b% = RND(N) : UNTIL b%<>a%
      PRINT '"Now swapping " mname$(a%) "'s and " mname$(b%) "'s partners:"
      SWAP mpartner%(a%), mpartner%(b%)
      PRINT mname$(a%) " is engaged to " wname$(mpartner%(a%))
      PRINT mname$(b%) " is engaged to " wname$(mpartner%(b%))
      PRINT "Relationships are ";
      IF FNstable PRINT "stable." ELSE PRINT "unstable."
      END
      
      DEF FNstable
      LOCAL m%, w%, o%, p%
      FOR m% = 1 TO N
        w% = mpartner%(m%)
        FOR o% = 1 TO N
          p% = wpartner%(o%)
          IF INSTR(mpref$(m%), LEFT$(wname$(o%),1)) < \
          \  INSTR(mpref$(m%), LEFT$(wname$(w%),1)) AND \
          \  INSTR(wpref$(o%), LEFT$(mname$(m%),1)) < \
          \  INSTR(wpref$(o%), LEFT$(mname$(p%),1)) THEN
            = FALSE
          ENDIF
        NEXT o%
      NEXT m%
      = TRUE

You may also check:How to resolve the algorithm Enumerations step by step in the Seed7 programming language
You may also check:How to resolve the algorithm File size step by step in the Smalltalk programming language
You may also check:How to resolve the algorithm Best shuffle step by step in the Picat programming language
You may also check:How to resolve the algorithm Problem of Apollonius step by step in the Racket programming language
You may also check:How to resolve the algorithm Queue/Definition step by step in the OCaml programming language