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 |
(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
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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] A polynomial time XSLT progra, Costello, Roger L. | Thread | Re: [xsl] A polynomial time XSLT pr, David Carlisle |
[xsl] A polynomial time XSLT progra, Costello, Roger L. | Date | Re: [xsl] A polynomial time XSLT pr, David Carlisle |
Month |