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