Re: Challenge! , mg[915],mg[917]

• To: mathgroup at christensen.cybernetics.net
• Subject: [mg986] Re: [mg889] Challenge! , mg[915],mg[917]
• From: hay at haystack.demon.co.uk
• Date: Thu, 4 May 1995 07:44:43 -0400

```Paul E Howland <PEHOWLAND at taz.dra.hmg.gb>[mg889] Challenge!
wrote:

> I have two lists of equal length M.
> I wish to generate a third list also of length M, where the i th
> element of this list is either the i th element of the first list,
> or the i th element of the second list.
> It should be equally probable that the new element be chosen from
> the first or second list.
He then gave a solution and asked for improvements.

David Wagner mg[915] and Lou Dandria mg[917] supplied essentially
the same improvement and generalized to any number of lists (their
code is give as  interleave  below (Dave's name))

Here are two faster codes: the techniques used are generally applicable.

interleave2 is a simple modification of interleave
interleave3 is a different code that is faster than interleave2;it
is an example of building up a preliminary structure and then
modifying it.

In[1]:=
interleave[s__List] :=
With[{len = Length[{s}]},
#[[Random[Integer, {1,len}]]]& /@ Transpose[{s}]
]

With takes time: it turns out not to be worth it. Admittedly Length
is only calculated once instead of as many times as the length of
the lists in  s___List; but Length is extremely quickly found.
Changing With to Block has very nearly the same effect as removing With.

Remove With.
In[2]:=
interleave2[s__List] :=
#[[Random[Integer, {1,Length[{s}]}]]]& /@ Transpose[{s}];

Timings:

Make sum test data
In[3]:=
test1 = Array[#,{30}]&/@(Range[10]);

In[4]:=
Do[interleave@@test1,{30}]//Timing//First
Do[interleave2@@test1,{30}]//Timing//First

Out[4]=
1.08333 Second
Out[5]=
0.8 Second

The advantage  is more marked with larger lists.
In[6]:=
test2 =Array[#,{300}]&/@(Range[100]);

In[7]:=
interleave@@test2//Timing//First
interleave2@@test2//Timing//First

Out[7]=
2.28333 Second
Out[8]=
0.916667 Second

(*Code for Interleave3*)
In[9]:=
interleave3[L:{s_,___}] :=
Transpose[
L[[Random[Integer,{1,Length[L]}]&/@s ]],
{1,1}
];
(*Transpose[m,{1,1}] gives the diagonal of matrix m*)
Check correctness

In[10]:=
test0 = Array[#,{8}]&/@Range[3]
Out[10]=
{{1[1], 1[2], 1[3], 1[4], 1[5], 1[6], 1[7], 1[8]},

{[1], 2[2], 2[3], 2[4], 2[5], 2[6], 2[7], 2[8]},

{3[1], 3[2], 3[3], 3[4], 3[5], 3[6], 3[7], 3[8]}}

In[11]:=
interleave3[test0]
Out[11]=
{1[1], 1[2], 3[3], 2[4], 2[5], 2[6], 3[7], 2[8]}

Timings (first for interleave2 second for interleave3)

In[12]:=
Do[interleave2@@test1,{30}]//Timing//First
Do[interleave3[test1],{30}]//Timing//First

Out[12]=
0.816667 Second
Out[13]=
0.483333 Second

The advantage with interleave3 is more marked with larger lists.

In[14]:=
interleave2@@test2//Timing//First
interleave3[test2]//Timing//First
Out[14]=
0.9 Second
Out[15]=
0.133333 Second

Interleave3 works as follows
In[16]:=
(L = {s,r,t}= test0)//TableForm
Out[16]//TableForm=
1[1]   1[2]   1[3]   1[4]   1[5]   1[6]   1[7]   1[8]

2[1]   2[2]   2[3]   2[4]   2[5]   2[6]   2[7]   2[8]

3[1]   3[2]   3[3]   3[4]   3[5]   3[6]   3[7]   3[8]

In[17]:=
choiceindices = Random[Integer,{1,Length[L]}]&/@s
Out[17]=
{2, 1, 3, 1, 1, 2, 1, 3}
In[18]:=
(choicelist = L[[choiceindices]])//TableForm
Out[18]//TableForm=
2[1]   2[2]   2[3]   2[4]   2[5]   2[6]   2[7]   2[8]

1[1]   1[2]   1[3]   1[4]   1[5]   1[6]   1[7]   1[8]

3[1]   3[2]   3[3]   3[4]   3[5]   3[6]   3[7]   3[8]

1[1]   1[2]   1[3]   1[4]   1[5]   1[6]   1[7]   1[8]

1[1]   1[2]   1[3]   1[4]   1[5]   1[6]   1[7]   1[8]

2[1]   2[2]   2[3]   2[4]   2[5]   2[6]   2[7]   2[8]

1[1]   1[2]   1[3]   1[4]   1[5]   1[6]   1[7]   1[8]

3[1]   3[2]   3[3]   3[4]   3[5]   3[6]   3[7]   3[8]

Take the diagonal of this matrix.

In[19]:=
Transpose[ choicelist,{1,1}]
Out[19]=
{2[1], 1[2], 3[3], 1[4], 1[5], 2[6], 1[7], 3[8]}

Block prevents the attempted evaluation of Part before threading.
In speed it is between interleave2 and interleave3.

In[20]:=
Clear[interleave4];
interleave4[L:{s_,___}] :=
Block[{Part},
Part[
L,Random[Integer,{1,Length[L]}]&/@s,
Range[Length[s]]
],
List,
-2   (*thread over any Lists amongst last 2 entries*)
]
]

Allan Hayes
hay at haystack.demon.co.uk

```

• Prev by Date: Re: MMA to BTM & Vice-Versa
• Next by Date: Mathematica Programming Reference Recommendation
• Previous by thread: Re: MMA to BTM & Vice-Versa
• Next by thread: Mathematica Programming Reference Recommendation