User:Realazthat/Notes/Scrap

From Rosetta Code

Du

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lcl} C & = & \text{Cycle modular sequence of vertices}\\ E & = & \text{Edges set/matrix}\\ F & = & \text{Former main breakpoints set/matrix}\\ u,v & = & \text{Vertices in a graph} \\ p,q,r,s & = & \text{Indices in a sequence}\\ (C_{p},C_{p-1}) & = & \text{Current main breakpoint}\\ \left[p,q\right] \in C & = & \text{Segment to cut, ranged from } p \text{ to } q \text{ in } C\\ \left(r,s\right) \in C & = & \text{Pair of neighboring vertices representing an edge to insert the segment in between}\\ b\left(E,u,v\right) \in \left\{0,1\right\} & = & \begin{cases} 0 & \text{if }\left(u,v\right) \in E\\ 1 & \text{if }\left(u,v\right) \notin E\end{cases}\\ f\left(EF,u,v\right) \in \left\{0,1\right\} & = & \begin{cases} 0 & \text{if }\left(u,v\right) \in F\\ 1 & \text{if }\left(u,v\right) \notin F\end{cases}\\ c\left(C,E,p,q,r,s\right)\in\left\{ 0,1,2,3\right\} & = & b\left(E,C_{p-1},C_{q+1}\right)+b\left(E,C_{q},C_{s}\right)+b\left(E,C_{p},C_{r}\right) \\ d\left(C,E,F,p,q,r,s\right)\in\left\{ 0,1,2,3\right\} & = & f\left(E,F,C_{p-1},C_{q+1}\right)+f\left(E,F,C_{q},C_{s}\right)+f\left(E,F,C_{p},C_{r}\right)\\ b,c,d,f \in O\left(1\right)\\ \end{array} }


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lcl} m\left(C,F,E,p \in C\right)\in\left\{0,1,2,3,\infty\right\} & = & \underset{\begin{array}{c} q,r,s \in C\\ \left(r \notin [p,q]\right) \wedge \left(s \notin [p,q] \right) \wedge \left(\left|s-r\right|=1 \right)\\ \left(c\left(C,E,p,q,r,s\right)\neq0\right)\rightarrow\left(d\left(C,E,F,p,q,r,s\right)\neq0\right)\end{array}} {\min} c\left(C,E,p,q,r,s\right)\\ \end{array} }

Naive algorithm

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m\left(C,F,E,p\right) \in O\left(\left|n\right|^2\right) } 


newedgdes(C,p,q,r,s):
  return { (C[p-1],C[q+1]), (C[q],C[s]), (C[p], C[r]) }

countbps(E,NE):
  newbps = 0
  for ( ne in NE )
    if ( ne !in E )
      ++newbps
  return newbps


countmainbps(F,E,NE):
  newmainbps = 0
  for ( ne in NE )
    if ( ne !in E && ne in F )
      ++newmainbps
  return newmainbps



m(C,F,E,p):
  min = infinity
  n = |C|
  for ( q in range(p,p-2) )
    for ( s in range( q + 2, p ) )
      r = s - 1
      for ( i in range(2) )
        NE = newedges(C,p,q,r,s)
        if ( |NE| != 0 )
          newbps = countbps(F,E,NE)
          newmainbps = countmainbps(F,E,NE)
          
          if ( newbps == 0 || newmainbps > 0 )
            min = newbps < min ? newbps : min
       
        swap(r,s)
  return min

Better algorithm

As we iterate over the different possible values for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} , there are incrementally more possibilities for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (r,s)} . Each selection of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (r,s)} implies a possible breakpoint for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p,r)} .

For each q, for all the valid (r,s) for that q, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_{q}} will track those that result in no breakpoint for (p,r).

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_{q} = \left\{ C_{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} \left[ b(E,C_{p},C_{r})=0 \right] \right\} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{q}} will track those s that result in a breakpoint that is a former main breakpoint.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{q} = \left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} \left[ b(E,C_{p},C_{r})=1 \wedge f(E,F,C_{p},C_{r})=1 \right] \right\} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{q} = \left\{ C{s} : s \notin [p,q] \wedge \exists_{r,|r-s|=1,r \notin [p,q]} \left[ b(E,C_{p},C_{r})=1 \wedge f(E,F,C_{p},C_{r})=0 \right] \right\} D_{q} = \left\{ v : (C_{q},v) \in E \right\} H_{q} = \left\{ v \in D_{q} : f(E,F,v,C_{q})=0 \right\} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lcl} W(q) \in \left\{0,1,2,3,\infty\right\} & = & \begin{cases} W_{0}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 0 \text{,}\\ W_{1}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 1 \wedge f(E,F,C_{p-1},C_{q+1}) = 0\text{,}\\ W_{2}(q) & \text{if } b(E,C_{p-1},C_{q+1}) = 1 \wedge f(E,F,C_{p-1},C_{q+1}) = 1 \end{cases}\\ W_{0} & = & \begin{cases} 0 & \text{if } \left|A_{q} / D_{q}\right| \not= 0 \text{,}\\ 1 & \left( \left|A_{q} / D_{q}\right| = 0 \right) \wedge \left( \left| C_{q} / D_{q} \right| \not=0 \vee \left|A_{q} \cup H_{q} \right| \not=0 \right) \end{cases}\\ \end{array} }

Retrieved from "https://rosettacode.org/wiki/User:Realazthat/Notes/Scrap?oldid=168846"