Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #5208

Re: 1-liner wanted

From "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: 1-liner wanted
Date 2011-09-25 09:43 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <j5mt3v$smf$1@smc.vnet.net> (permalink)
References <j5hdfe$7j5$1@smc.vnet.net>

Show all headers | View raw


On Fri, 23 Sep 2011 08:45:50 +0100, Kent Holing <KHO@statoil.com> wrote:

> Let's assume we have a list of elements of the type {x,y,z} for x, y and  
> z integers. And, if needed we assume x < y < z. We also assume that the  
> list contains at least 3 such triples.
>
> Can Mathematica easily solve the following problem? To detect at least  
> three elements from the list of the type {a,b,.}, {b,c,.} and {a,c,.}? I  
> am more intereseted in an elegant 1-liner than computational efficient  
> solutions.
>
> Example:
> Givenlist ={1,2,3},{2,4,5],{6,7,8},{1,4,6},{7,8,9},{11,12,13}};
> should return
> {{1,2,3},{2,4,5},{1,4,6}}
>
> Kent Holing,
> Norway
>

The following is a brute-force approach; while short and easy to  
understand it is far from computationally efficent. As the concept of a  
line of code is not very well defined in Mathematica, I will leave it to  
you to decide whether or not it constitutes a one-liner.

f[list_] := ReplaceList[
  list,
  Apply[
   Alternatives,
   Permutations[
    {f:{a_, b_, _}, g:{b_, c_, _}, h:{a_, c_, _}},
    {3}
   ] /. {f_, g_, h_} :> {___, f, ___, g, ___, h, ___}
  ] :> {f, g, h}
]

list = {
  {1, 2, 3}, {2, 4, 5}, {6, 7, 8},
  {1, 4, 6}, {7, 8, 9}, {11, 12, 13}
};

f[list]

gives

{{{1, 2, 3}, {2, 4, 5}, {1, 4, 6}}}

which is a list of instances of the required sequence of items. In this  
case there is only one element in the list returned because there is only  
one possibility for the given input. For other lists multiple matches may  
be possible. Trying it on a slightly longer list:

f@RandomInteger[{0, 9}, {10, 3}]

gives

{
  {{6, 0, 2}, {0, 3, 4}, {6, 3, 1}},
  {{6, 8, 9}, {8, 3, 4}, {6, 3, 1}},
  {{5, 6, 6}, {6, 0, 2}, {5, 0, 5}}
}

showing three possible matches for this particular input. For longer  
lists, the number of matches can be rather large; there are about 1000  
possibilities for a list of 100 random triples and finding them all can  
take some time (over a second on my computer). If you have at most one  
matching instance in any given list, or only require the first matching  
instance to be returned, you might wish to substitute Replace for  
ReplaceList.

Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Find similar | Unroll thread


Thread

1-liner wanted Kent Holing <KHO@statoil.com> - 2011-09-23 07:45 +0000
  Re: 1-liner wanted "andre.robin3" <andre.robin3@wanadoo.fr> - 2011-09-25 02:37 +0000
  Re: 1-liner wanted Peter Pein <petsie@dordos.net> - 2011-09-25 02:40 +0000
  Re: 1-liner wanted Ray Koopman <koopman@sfu.ca> - 2011-09-25 02:42 +0000
  Re: 1-liner wanted "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> - 2011-09-25 09:43 +0000

csiph-web