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

Re: removing sublist . Again and Different

• To: mathgroup at smc.vnet.net
• Subject: [mg56342] Re: removing sublist . Again and Different
• From: "Carl K. Woll" <carlw at u.washington.edu>
• Date: Fri, 22 Apr 2005 06:23:31 -0400 (EDT)
• Organization: University of Washington
• References: <d47tgv$575$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

"giampi1960" <giampiero1960 at yahoo.com> wrote in message 
news:d47tgv$575$1 at smc.vnet.net...
> hello i read borges2003xx at yahoo.it meassage :
>
>
>>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
>
>
> i ask your help for faster way to do the opposite
> f[x]:=  {..,{1,2,3,4},..,{2,3},..} removes {1,2,3,4}.
>
> best regards
>
> giampiero
>

I will assume that every sublist contains only positive integers, with no 
duplicates. If duplicates are allowed, then a modification of my prime 
approach given in an earlier respone to giorgio will suffice. If the 
sublists can contain objects other than integers, then a modification of my 
first solution to giorgio's question will be necessary.

With sublists containing only positive integers, with no duplicates, then we 
have a bijection between sublists and integers where the bit representation 
of an integer contains a 1 at position 2^(n-1) if n is included in the 
sublist, and a 0 if n is not in the sublist. Then, a subset test can be 
obtained using BitAnd and BitNot. Finally, we want the sublists to be 
partially ordered, so that if x and y are two sublists with x being a subset 
of y, then x comes before y. Then, we can go through the list, and add 
sublists which do not contain any of the previous sublists. The partial 
ordering ensures that every sublist added will not need to be removed later. 
The following function encapsulates these ideas.

elim[n_]:=Module[{},
 p=Union[Plus@@@(2^(n-1))];
 ans=Fold[addmem,{First@p},Rest@p];
 Flatten@Position[Reverse@IntegerDigits[#,2],1]&/@ans
 ]

addmem[x_,a_]:=If[Min@BitAnd[x,BitNot[a]]==0,x,Append[x,a]]

Carl Woll