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