[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
Prev by Date:
**Re: Re: multiple 3d plots**
Next by Date:
**Re: Re: (x-y) DiracDelta[x-y] does not simplify to 0**
Previous by thread:
** Re: removing sublist . Again and Different**
Next by thread:
**Re: removing sublist . Again and Different**
| |