Permanent Computation Efficiency

• To: mathgroup at smc.vnet.net
• Subject: [mg105035] Permanent Computation Efficiency
• From: Sunt <sunting.05 at gmail.com>
• Date: Wed, 18 Nov 2009 07:00:53 -0500 (EST)

```Hi All,
Recently I've been dealing with one problem of permanent computation
and got puzzled about two algorithms on it.

I've find a defined function from Mathworld(http://
mathworld.wolfram.com/Permanent.html) as bellow:
Permanent[m_List] := With[{v = Array[x, Length[m]]}, Coefficient[Times
@@ (m.v), Times @@ v]]
Meanwhile, according to Laplace Expansion Theorem, we have another
function for permanent computation(expanding a permanent by the first
row):
LPermanent[m_List?(Length[#] == 1 &)] := Flatten[m] // First;
LPermanent[m_List] := Module[  {n = Length[m], v, mm},
v = m[[All, 1]];
mm = m[[All, 2 ;; -1]];
(v.Table[LPermanent[Delete[mm, i]], {i, n}])
]

Comparison of the two functions is quite interesting but puzzling, the
former is much better than the other.
Running the two function with the same 10*10 matrix with Timing[]
appended, the former finished in 0.s while the other a much slower
779.912s!
However, according to the computation complexity analysis, the latter
is expected as a better one.

Is there something I didn't understand about?