[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

[xsl] A polynomial time XSLT program that generates a list of compatible roommates?

---

---

Hi Folks,

Problem: you are given a list of freshmen, together with which ones are
willing to room with which other ones. Pair off as many willing roommates as
possible.

The following XML document lists the names of freshmen and then shows for each
freshmen the names of other freshmen they are willing to roommate with (i.e.,
compatible with):

----------------------------------------------
         PairFreshmen.xml
----------------------------------------------
<RoommateFinder>
    <Freshmen>
        <Name>Sally</Name>
        <Name>Joan</Name>
        <Name>Betsy</Name>
        <Name>Linda</Name>
        <Name>Sue</Name>
        <Name>Carol</Name>
        <Name>Francine</Name>
        <Name>Doris</Name>
    </Freshmen>
    <CompatiblePairs>
        <Pair>
            <Name>Betsy</Name>
            <OkayToPairWith>
                <Name>Joan</Name>
                <Name>Sue</Name>
                <Name>Francine</Name>
            </OkayToPairWith>
        </Pair>
        <Pair>
            <Name>Francine</Name>
            <OkayToPairWith>
                <Name>Carol</Name>
                <Name>Sue</Name>
                <Name>Sally</Name>
                <Name>Joan</Name>
                <Name>Doris</Name>
            </OkayToPairWith>
        </Pair>
        <Pair>
            <Name>Sue</Name>
            <OkayToPairWith>
                <Name>Carol</Name>
                <Name>Francine</Name>
                <Name>Betsy</Name>
            </OkayToPairWith>
        </Pair>
        <Pair>
            <Name>Sally</Name>
            <OkayToPairWith>
                <Name>Joan</Name>
                <Name>Betsy</Name>
                <Name>Carol</Name>
            </OkayToPairWith>
        </Pair>
        <Pair>
            <Name>Joan</Name>
            <OkayToPairWith>
                <Name>Betsy</Name>
                <Name>Linda</Name>
            </OkayToPairWith>
        </Pair>
        <Pair>
            <Name>Linda</Name>
            <OkayToPairWith>
                <Name>Joan</Name>
            </OkayToPairWith>
        </Pair>
        <Pair>
            <Name>Carol</Name>
            <OkayToPairWith>
                <Name>Sally</Name>
            </OkayToPairWith>
        </Pair>
        <Pair>
            <Name>Doris</Name>
            <OkayToPairWith>
                <Name>Francine</Name>
            </OkayToPairWith>
        </Pair>
    </CompatiblePairs>
</RoommateFinder>

Betsy is willing to room with Joan and Joan is willing to room with Betsy, so
that is a potential pairing.

Below is an XSLT program that generates all possible pairings. It determined
that this, among others, is a potential pairing of freshmen:

{ Francine ,  Doris }  { Betsy ,  Sue }  { Joan ,  Linda }  { Sally ,  Carol
}

The XSLT program does a brute-force search. The time it requires to find all
the compatible pairs of freshmen is exponential, N^N. (Yikes!)

I have read that there is a polynomial time algorithm for this problem. Do you
have ideas on how to solve this problem in polynomial time?

----------------------------------------------
         PairFreshmen.xsl
----------------------------------------------
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:map="http://www.w3.org/2005/xpath-functions/map"
                xmlns:math="http://www.w3.org/2005/xpath-functions/math"
                xmlns:xs="http://www.w3.org/2001/XMLSchema"
                xmlns:f="function"
                version="3.0">

    <xsl:output method="text"/>

    <xsl:variable name="names" select="/RoommateFinder/Freshmen/Name" />
    <xsl:variable name="compatible-pairs"
select="/RoommateFinder/CompatiblePairs" />

    <xsl:template match="/">
        <xsl:value-of
select="f:show-all-compatible-pairs(count(/RoommateFinder/Freshmen/Name))" />
    </xsl:template>

    <!--
            We wish to generate all lists of compatible pairs. The brute force
approach
            is to generate every possible sequence of persons and then pair
the
            first person to the second person, the third person to the fourth
person,
            the fifth person to the sixth person, and so on. Output the
sequence
            if the students are compatible in each pair.

            for person1 = (Sally, Joan, Betsy, Linda, Sue, Carol, Francine,
Doris)
                for person2 = (Sally, Joan, Betsy, Linda, Sue, Carol,
Francine, Doris)
                    for person3 = (Sally, Joan, Betsy, Linda, Sue, Carol,
Francine, Doris)
                        for person4 = (Sally, Joan, Betsy, Linda, Sue, Carol,
Francine, Doris)
                            for person5 = (Sally, Joan, Betsy, Linda, Sue,
Carol, Francine, Doris)
                                for person6 = (Sally, Joan, Betsy, Linda, Sue,
Carol, Francine, Doris)
                                    for person7 = (Sally, Joan, Betsy, Linda,
Sue, Carol, Francine, Doris)
                                        for person8 = (Sally, Joan, Betsy,
Linda, Sue, Carol, Francine, Doris)
                                            if (compatible person1 person2)
and
                                               (compatible person3 person4)
and
                                               (compatible person5 person6)
and
                                               (compatible person7 person8)
then
                                                  Output: {person1, person2},
                                                          {person3, person4},
                                                          {person5, person6},
                                                          {person7, person8}

            The number of iterations is: 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 = 8^8
            The number of iterations for N persons is N^N
            Wow! That is an exponential number of iterations.
        -->

    <xsl:function name="f:show-all-compatible-pairs">
        <xsl:param name="N" as="xs:integer" />

        <!-- Total number of iterations is N^N -->

        <xsl:variable name="total" select="xs:integer(math:pow($N, $N) - 1)"
as="xs:integer" />

        <xsl:for-each select="0 to $total">
            <xsl:variable name="number" select="." as="xs:integer" />
            <!--
                $number is an encoding of a sequence of students.
                $number = 0 represents (Sally, Sally, Sally, Sally, Sally,
Sally, Sally, Sally)
                $number = 1 represents (Sally, Sally, Sally, Sally, Sally,
Sally, Sally, Joan)
                $number = 2 represents (Sally, Sally, Sally, Sally, Sally,
Sally, Sally, Betsy)
                $number = 3 represents (Sally, Sally, Sally, Sally, Sally,
Sally, Sally, Linda)
                ...
                $number = 8 represents (Sally, Sally, Sally, Sally, Sally,
Sally, Joan, Sally)
                ...
                $number = $total represents (Doris, Doris, Doris, Doris,
Doris, Doris, Doris, Doris)
                The purpose of the following iterate loop is to decode
$number. This is achieved
                as follows:
                $N is the number of students
                Iterate from i = 1 to $N
                    $num is a value in the range 0 .. $total
                    The i'th student in the sequence is the student whose
                    position() (offset by 1) equals $num mod $N
            -->
            <xsl:iterate select="1 to $N">
                <xsl:param name="num" select="$number" as="xs:integer" />
                <xsl:param name="pairs" select="()" as="xs:string*" />

                <xsl:variable name="remainder" select="$num mod $N"
as="xs:integer" />

                <xsl:variable name="student" select="$names[(position() - 1)
eq $remainder]" />

                <xsl:next-iteration>
                    <xsl:with-param name="num" select="$num idiv $N" />
                    <xsl:with-param name="pairs" select="($pairs, $student)"
/>
                </xsl:next-iteration>
                <xsl:on-completion>
                    <xsl:variable name="pair1" select="$pairs[position() mod 2
= 0]" />
                    <xsl:variable name="pair2" select="$pairs[position() mod 2
= 1]" />
                    <xsl:if test="f:all-pairs-are-compatible($pair1, $pair2)
eq true()">
                        <xsl:value-of select="f:print-pairs($pair1, $pair2)"
/>
                    </xsl:if>
                </xsl:on-completion>
            </xsl:iterate>
        </xsl:for-each>
    </xsl:function>

    <xsl:function name="f:all-pairs-are-compatible" as="xs:boolean">
        <xsl:param name="pair1" as="xs:string*" />
        <xsl:param name="pair2" as="xs:string*" />

        <xsl:choose>
            <xsl:when test="count($pair1) ne count($pair2)">
                <xsl:value-of select="false()" />
            </xsl:when>
            <xsl:otherwise>
                <xsl:iterate select="$pair1">
                    <xsl:variable name="posn" select="position()" />
                    <xsl:variable name="compatible" select="f:compatible(.,
$pair2[position() eq $posn])" as="xs:boolean" />
                    <xsl:if test="$compatible eq false()">
                        <xsl:break>
                            <xsl:value-of select="false()" />
                        </xsl:break>
                    </xsl:if>
                    <xsl:on-completion>
                        <xsl:value-of select="true()" />
                    </xsl:on-completion>
                </xsl:iterate>
            </xsl:otherwise>
        </xsl:choose>

    </xsl:function>

    <xsl:function name="f:compatible" as="xs:boolean">
        <xsl:param name="name1" as="xs:string" />
        <xsl:param name="name2" as="xs:string" />

        <xsl:value-of select="($name2 = $compatible-pairs/Pair[Name eq
$name1]/OkayToPairWith/Name) and
                              ($name1 = $compatible-pairs/Pair[Name eq
$name2]/OkayToPairWith/Name)" />

    </xsl:function>

    <xsl:function name="f:print-pairs" as="xs:string*">
        <xsl:param name="pair1" as="xs:string*" />
        <xsl:param name="pair2" as="xs:string*" />

        <xsl:if test="count($pair1) eq count(distinct-values($pair1)) and
                      count($pair2) eq count(distinct-values($pair2)) and
                      count(($pair1, $pair2)) eq
count(distinct-values(($pair1, $pair2)))">
            <xsl:text>Compatible Roommates: </xsl:text>
            <xsl:for-each select="$pair1">
                <xsl:text>{</xsl:text>
                <xsl:value-of select="." />
                <xsl:text>, </xsl:text>
                <xsl:variable name="posn" select="position()" />
                <xsl:value-of select="$pair2[position() eq $posn]" />
                <xsl:text>} </xsl:text>
            </xsl:for-each>
<xsl:text>
</xsl:text>
        </xsl:if>

    </xsl:function>

</xsl:stylesheet>

---