MathGroup Archive 2000

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

Search the Archive

Re: fastest way to do pair-sum / make pair-list

  • To: mathgroup at smc.vnet.net
  • Subject: [mg23231] Re: [mg23170] fastest way to do pair-sum / make pair-list
  • From: Carl Woll <carlw at u.washington.edu>
  • Date: Tue, 25 Apr 2000 01:40:34 -0400 (EDT)
  • Organization: Physics Department, U of Washington
  • References: <200004210348.XAA19772@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Hi Wijnand,

I'll just discuss pair creation here. The builtin mathematica code to do
what you want is KSubsets from the Discrete`Combinatorica` package.
However, this is significantly slower than your methods. So, consider your
two methods. Your second method just needs a little tweaking to be
equivalent to your first method. Just use the two argument version of
Flatten, as in

topairs[lst_] :=
  Module[{l = Length[lst]},
    Flatten[Table[lst[[{i, j}]], {i, 1, l - 1}, {j, i + 1, l}], 1]]

Now, I was able to come up with a more efficient pair creation program. The
basic idea is to first create all the pairs, and then select only the pairs
that you want. The creation of all the pairs is most simply done by using
Outer and then Flattening. To select just the pairs you want, I created a
mask. So, my program is as follows:

In[30]:=
mask[n_] := Module[{r = Range[n - 1]},
    Flatten[Range @@@ Transpose[{r(n + 1) - (n - 1), r n}]]]

In[42]:=
pairs[n_List] := Module[{m, allpairs},
    m = mask[Length[n]];
    allpairs = Flatten[Outer[List, n, n], 1];
    allpairs[[m]]]

The mask code selects the upper triangular portion of an n x n matrix. Then
in the pairs code, allpairs is all of the pairs, and allpairs[[m]] selects
the pairs we want. In my testing, pairs[Range[100]] was about 3 times
faster than the topairs code above. Depending on the nature of the lists
you are working with, you may get an additional boost by compiling the
above code.

Carl Woll


Wijnand Schepens wrote:

> 1.
>
> What is the most efficient way to calculate the sum
>
> Sum f [ (x[[i]]-x[[j]])^2 ]
> i<j
>
> ??
>
> Example:
>
> I have a vector of real numbers:
> lst = N[Range[100]];
> and a function operating on a number:
> f[r2_]:=(r2-1.0)^2
>
> Is
>
> Sum[  Sum[  f [ (lst[[i]]-lst[[j]])^2 ] , {j,i+1,Length[lst]}],
> {i,1,Length[lst-1]}]
>
> the fastest way??
>
> This kind of sum is very common in Molecular Modelling, where the total
> energy of a system is often a sum of pair-energies, which only depend on
> the distance between atoms.
> I was surprised that I didn't find anything on sums over pairs in
> Mathematica...
>
> 2.
>
> What is the most efficient way to generate a list of pairs starting from
> a list??
> Is there a standard Mathematica routine which does this?
>
> e.g.  {a,b,c,d} ----> {{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}}
>
> or {x1,x2,...} -----> { {xi,xj} ...}
> with i<j
>
> Best solution I found was
> topairs[lst_] :=
>   Module[{l=Length[lst]},
>      Map[(Sequence @@ #1) &,
>              Table[ lst [[{i, j}]], {i, 1, l - 1}, {j, i + 1, l}]
>      ]
>   ]
>
> Another possibility would be
> topairs2[lst_] :=
>   Module[{l = Length[lst]},
>     Partition[
>        Flatten[
>            Table[ lst[[{i, j}]], {i, 1, l - 1}, {j, i + 1, l}]
>        ], 2
>     ]
>  ]
>
> but this doesn't have the same effect if operating on a list of lists
>   topairs[{{a1, a2}, {b1, b2}, {c1, c2}}]
> gives what we want,
>   topairs2[{{a1, a2}, {b1, b2}, {c1, c2}}]
> not



  • Prev by Date: Re: Re: A simple programming question.
  • Next by Date: RE: Re: Plotting bounded domains
  • Previous by thread: Re: fastest way to do pair-sum / make pair-list
  • Next by thread: Re: fastest way to do pair-sum / make pair-list