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

MathGroup Archive 2007

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

Search the Archive

Re: Re: Binary Vector Manipulation

  • To: mathgroup at smc.vnet.net
  • Subject: [mg84142] Re: [mg84103] Re: Binary Vector Manipulation
  • From: DrMajorBob <drmajorbob at bigfoot.com>
  • Date: Tue, 11 Dec 2007 06:12:03 -0500 (EST)
  • References: <fjj183$frv$1@smc.vnet.net> <14456678.1197348854887.JavaMail.root@m35>
  • Reply-to: drmajorbob at bigfoot.com

Jean-Marc,

There are typos in the signature on the left, where you need (0|1).. or 
(0|1)..., not 0|1 __.

Here's a corrected version:

Clear[myFun, brt]
myFun[A : {(0 | 1) ..}, target : {(0 | 1) ..}] /;
   Length@A <= Length@target && EvenQ@Length@target :=
  Module[{B = target, len = Length@target, pos},
   B = ReplacePart[B, Position[A, 1] -> 1];
   While[Count[B, 1] - len/2 > 0, pos = RandomInteger[{1, len}];
    If[B[[pos]] == 1, B[[pos]] = 0];];
   B]

I'm not sure that does what the OP wanted anyway, but if it does, myFun's  
complexity is poor because of the While loop.

So here's a better way to do exactly the same thing (I think):

brt[a : {(0 | 1) ...}, b : {(0 | 1) ...}] /;
   Length@a <= Length@b && EvenQ@Length@b :=
  Module[{and, excess},
   and = BitOr[PadRight[a, Length@b], b];
   excess = Sort[Flatten@Position[and, 1], RandomReal[] < 1/2 &];
   pos = Take[excess, 1/2 Length@b - Length@excess];
   ReplacePart[and, Thread[pos -> 0]]
   ]

and some Timing tests:

test[n_] :=
  Module[{a = RandomChoice[{95, 5}/100 -> {0, 1}, n],
    b = RandomChoice[{1, 1}/2 -> {0, 1}, n]},
   Column@{Row@{"totals: ", Total /@ {a, b, BitOr[a, b]}},
     Row@{"myFun: ", Timing@Tally@myFun[a, b]},
     Row@{"brt: ", Timing@Tally@brt[a, b]}}
   ]

test[10^3]

totals: {53,491,523}
myFun: {2.39531*10^-14,{{1,500},{0,500}}}
brt: {0.016,{{1,500},{0,500}}}


test[10^4]

totals: {437,4987,5212}
myFun: {0.343,{{0,5000},{1,5000}}}
brt: {0.188,{{0,5000},{1,5000}}}


test[10^5]

totals: {5003,49963,52437}
myFun: {36.047,{{1,50000},{0,50000}}}
brt: {2.5,{{1,50000},{0,50000}}}

Here's a test of brt alone, since myFun would take too long for 10^6  
entries:

n=10^6;
Module[{a=RandomChoice[{95,5}/100->{0,1},n],b=RandomChoice[{1,1}/2->{0,1},n]},
Column@{Row@{"totals: ",Total/@{a,b,BitOr[a,b]}},Row@{"brt:  
",Timing@Tally@brt[a,b]}}
]
totals: {50301,500809,526132}
brt: {29.953,{{0,500000},{1,500000}}}

It appears that brt is O[n] and myFun is O[n^2] (or a little worse, in  
both cases).

Bobby

On Mon, 10 Dec 2007 19:34:41 -0600, Jean-Marc Gulliet  
<jeanmarc.gulliet at gmail.com> wrote:

> Tara.Ann.Lorenz at gmail.com wrote:
>> I am need of assistance programming the following scenario:
>>
>> I have two vectors composed of 0's and 1's.  Vector "A" has 5% 1's
>> (and 95% 0's) while Vector "B" has 50% 1's and 50% 0's.
>>
>> First, I would like to change Vector B to have a "1" in every place
>> that Vector A also has a "1" (in other words, I will then have more
>> than 50% 1's in Vector B once this step is completed).
>>
>> Then, I would like to *randomly* return Vector B back to a 50/50
>> distribution of 1's and 0's.
>>
>> I greatly appreciate any proposed programming methods.
>
> The following function should do what you are asking for.
>
> In[1]:= myFun[A : {0 | 1 __}, target : {0 | 1 __}] /;
>    Length@A <= Length@B && EvenQ[Length@B] :=
>   Module[{B, len, pos},
>    B = target;
>    len = Length@B;
>    B = ReplacePart[B, Position[A, 1] -> 1];
>    While[Count[B, 1] - len/2 > 0,
>     pos = RandomInteger[{1, len}];
>     If[B[[pos]] == 1, B[[pos]] = 0];
>     ];
>    B
>    ]
>
> Then, we make up some data and check that myFun works correctly.
>
> In[2]:= Needs["Combinatorica`"]
> A = RandomPermutation[Join[Table[1, {5}], Table[0, {95}]]];
> B = RandomPermutation[Join[Table[1, {50}], Table[0, {50}]]];
> c = myFun[A, B];
> c == B
> Count[#, 1] & /@ {A, B, c}
>
> Out[6]= False
>
> Out[7]= {5, 50, 50}
>
> Regards,



-- =

DrMajorBob at bigfoot.com


  • Prev by Date: Re: Prefix Forms on the BasicMath Palette
  • Next by Date: Re: FullSimplify with Pi
  • Previous by thread: Re: Binary Vector Manipulation
  • Next by thread: Re: Re: Binary Vector Manipulation