Services & ResourcesWolfram ForumsMathGroup Archive

[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