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

[David Carlisle <davidc@xxxxxxxxx>]

I think you want

$ saxon9 rm.xml rm.xsl
[Sally,Betsy] [Joan,Linda] [Sue,Carol] [Francine,Doris]
[Sally,Carol] [Joan,Linda] [Betsy,Sue] [Francine,Doris]


where rm.xml is your posted file and the xsl is

<xsl:stylesheet version="2.0"
		xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
		xmlns:f="data:,f">

<xsl:output method="text"/>

<xsl:template match="RoommateFinder">
  <xsl:sequence select="string-join(f:rm(Freshmen/Name),'&#10;')"/>
</xsl:template>

<xsl:key name="p" match="OkayToPairWith/Name" use="../../Name"/>

<xsl:function name="f:rm">
 <xsl:param name="l"/>
  <xsl:sequence select="
  if(empty($l)) then ('')
  else if (empty(key('p',$l[1],root($l[1]))[.=$l])) then ()
  else
   for $p in key('p',$l[1],root($l[1]))[.=$l]
   return
   for $s in f:rm($l[position()!=1][not(.=$p)])
   return
   concat('[',$l[1],',',$p,'] ',$s)"/>
</xsl:function>

</xsl:stylesheet>


If it's time complexity is too large, just blame Michael's optimiser:-)


David