Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Exact Cover

  • To: mathgroup at smc.vnet.net
  • Subject: [mg88319] Re: Exact Cover
  • From: Szabolcs <szhorvat at gmail.com>
  • Date: Thu, 1 May 2008 06:27:30 -0400 (EDT)
  • References: <fvbr62$pl5$1@smc.vnet.net>

On May 1, 9:23 am, Johum <tuyenthanh101... at yahoo.com> wrote:
> Hello All,
>
> Someone can help me with this function?
>
> ExactCover[matrix]
>
> finds all subsets of rows of the rectangular matrix which have exactly one nonzero element in each column.
>
> matr = {{0, 0, 1, 0, 1, 1, 0},
>         {1, 0, 0, 1, 0, 0, 1},
>         {0, 1, 1, 0, 0, 1, 0},
>         {1, 0, 0, 1, 0, 0, 0},
>         {0, 1, 0, 0, 0, 0, 1},
>         {0, 0, 0, 1, 1, 0, 1}}
>
> ExactCover[matr]
>
> {{{1, 4}, {3, 5, 6}, {2, 7}}}
>


You did not say what the question was.  If you're looking for an
implementation, here's one:

http://www.imtek.de/simulation//mathematica/IMSweb/imsTOC/Game%20Theory/ExactCoverDocu.html


  • Prev by Date: Convert funcion
  • Next by Date: Re: function to check if array is empty
  • Previous by thread: Exact Cover
  • Next by thread: crosshatch shading