MathGroup Archive 2007

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

Search the Archive

Re: longest chain! is that a DFS?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg78797] Re: longest chain! is that a DFS?
  • From: dh <dh at metrohm.ch>
  • Date: Tue, 10 Jul 2007 06:22:59 -0400 (EDT)
  • References: <f6siaj$86s$1@smc.vnet.net>


Hi,

this can be done by:

-write a pair like {a,b}.

- all sequences of length 2 are equqal to B1

- increase sequence length by 1

- Nest until maximal length

here is an example (note that B3 and S[[3]] differ, I am using B3):

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

{{1,4},{2,8},{4,5},{6,7}},

{{8,1},{8,5},{7,8}},

{{5,6},{8,5}}};

NextStep[dat_,s_]:= Sequence @@ Cases[s,{#[[-1]],x_}->Append[#,x]]&/@ dat;

i=1; Nest[NextStep[#,s[[++i]]]&,s[[1]],3]

this gives:

{{1,2,8,5,6},{5,6,7,8,5}}

hope this helps, Daniel







mumat wrote:

> Hi there Everyone,

> 

> Here is my question.

> 

> Assume S is the set {B1,B2,...,Bn} where Bi's are non-empty sets of

> ordered pairs of A={1,2,3,...,8} ( <---  for simplicity).

> 

> our goal is to list all sequences of the form

> 

> X_1,X2,X3,X_4,...,X_m over A

> 

> of m, the longest possible length for which

> 

> 

> for every i: (X_i, X_(i+1)) is in B_i        AND        (X_(i+1),X_(i

> +2)) is in B_(i+1).

> 

> 

> For instance, ( with Notation: ab:={a,b})

> 

> S={ {12,23,24,56}, {14,28,45,67},{81,15,78}, {56,85} }, so

> 

> 

> B1={12,23,24,56},B2={14,28,45,67},B3={81,85,78},B4={52,85}.

> 

> 

> seq: 1,2,8,5,2 is of longest possible length 5.

> 

> 2,4,8,5,2 is another sequence of longest length.

> 

> 

> Any help would be greatly appreciated.

> 

> Best regards,

> 

> chekad sarami

> 

> 




  • Prev by Date: Re: Axes and Frame
  • Next by Date: Re: Frames and Axes
  • Previous by thread: longest chain! is that a DFS?
  • Next by thread: Re: longest chain! is that a DFS?