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

Subject: Re: [xsl] A polynomial time XSLT program that generates a list of compatible roommates?
From: sean@xxxxxxxxxxxxxxxxx
Date: Sun, 22 Sep 2013 17:49:42 -0600
Roger,

You can find Irving's algorithm at:

  (1) http://eprints.gla.ac.uk/11/1/SRT.pdf;
  (2) http://en.wikipedia.org/wiki/Stable_roommates_problem; and
  (3) http://www.sciencedirect.com/science/article/pii/0196677485900331


Faithfully, Sean B. Durkin


On 2013-09-22 09:49, Costello, Roger L. wrote:
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>

Current Thread