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