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
>
>