[Date Index]
[Thread Index]
[Author Index]
Re: removing subelements
*To*: mathgroup at smc.vnet.net
*Subject*: [mg56145] Re: removing subelements
*From*: "Carl K. Woll" <carlw at u.washington.edu>
*Date*: Sat, 16 Apr 2005 03:53:25 -0400 (EDT)
*Organization*: University of Washington
*References*: <d3o0ta$bqn$1@smc.vnet.net>
*Sender*: owner-wri-mathgroup at wolfram.com
<borges2003xx at yahoo.it> wrote in message news:d3o0ta$bqn$1 at smc.vnet.net...
> i'm a newbie. How implement the _faster functon_ which removes in a
> list every element that are a subelement.
> which means
> f[x]:= {..,{1,2,3,4},..,{2,3},..} removes {2,3}.
> thanx a lot.
> giorgio borghi
>
The first idea I had was to sort the elements in reverse order, and then to
go through the list one by one, deleting elements which are contained in
previous elements. Alternatively, you could take the first element in the
reverse sorted list, and then delete all elements which are contained in
that first element. Then, take this reduced set, and delete all elements
which are contained in its first element, and so on. For data, I used
variations of the following
data = Union /@ Table[ Table[Random[Integer, {1, 20}], {Random[Integer, {1,
10}]}], {10^3}];
Below, elim1 uses the first idea and elim2 uses the second. In my tests,
elim1 is quicker.
elim1[x_]:=Module[{pr},
pr=Reverse[Union[x]];
Fold[addmem1,{First@pr},Rest@pr]
]
addmem1[x_,a_]:=If[MemberQ[x,_?(Complement[a,#]=={}&)],x,Append[x,a]]
elim2[x_]:=Module[{pr},
acc=h[];
pr=Reverse[Union[x]];
NestWhile[sieve1,pr,#=!={}&];
List@@Flatten[acc]
]
sieve1[x_]:=(acc=h[acc,First@x];
DeleteCases[Rest@x,a_/;Complement[a,First@x]==={}])
In the above, Sow/Reap would probably speed up the sieve1 function.
If your data elements are always lists of integers (as in your example),
then a faster approach might be possible. Suppose your lists of integers
consisted of only primes. Then, if we multiply all the integers in a list
together, we can test for set membership by using the Mod function. If the
lists don't consist of primes, it is easy enough to turn it into a list of
primes by replacing the integer i in the list with the ith prime. Below, I
modify elim1 and elim2 to use this idea.
elim3[x_]:=Module[{pr},
pr=Reverse[Union[Times@@@Prime[x]]];
pr=Fold[addmem2,{First@pr},Rest@pr];
PrimePi[ FactorInteger[ Flatten[pr] ][[All,All,1]] ]
]
addmem2[x_,a_] := If[Min[Mod[x,a]]==0, x, Append[x,a]]
elim4[x_]:=Module[{pr},
acc={};
pr=Reverse[Union[Times@@@Prime[x]]];
NestWhile[sieve2,pr,#=!={}&];
PrimePi[ FactorInteger[Flatten[acc]][[All,All,1]] ]
]
sieve2[x_]:=(acc={acc,First@x}; Rest[x][[
Flatten@Position[Sign[Mod[First@x,Rest@x]],1] ]])
In the above, sieve2 can probably be sped up by using Sow/Reap and by using
Pick. At any rate, in my tests elim3 and elim4 are significantly faster than
elim1 and elim2. This time however, depending on the kind of data, elim3 or
elim4 can be the quickest.
Carl Woll
Prev by Date:
**Re: Re: SSH Remote Kernel on Windows - Can it be done?**
Next by Date:
**Re: Re: Re: Infinite sum of gaussians**
Previous by thread:
**Re: removing subelements**
Next by thread:
** Trouble with Limit[I ... k]/k, k-> Infinity]**
| |