Non-continuous subsequences: Difference between revisions
→{{header|F_Sharp|F#}}
Line 865:
=={{header|F_Sharp|F#}}==
===Generate only the non-continuous subsequences===
<lang fsharp>
(*
Line 890 ⟶ 891:
Counting the number of non-continuous subsequences is interesting:
<pre>
> Seq.length (N
Real: 00:00:00.169, CPU: 00:00:00.169, GC gen0: 0, gen1: 0
val it : int =
> Seq.length (N 10);;▼
val it : int = 968▼
> Seq.length (N 23);;
Real: 00:00:01.238, CPU: 00:00:01.239, GC gen0: 0, gen1: 0
val it : int = 8388331
> Seq.length (N
Real: 00:00:02.520, CPU: 00:00:02.523, GC gen0: 0, gen1: 0
val it : int =
Real: 00:00:04.926, CPU: 00:00:04.930, GC gen0: 0, gen1: 0
val it : int = 33554106
</pre>
===Generate all subsequences and filter out the continuous===
<lang fsharp>
(*
A function to filter out continuous subsequences.
Nigel Galloway July 24th., 2017
*)
let Nonseq n=
let fn = function
|((n,0),true )->(n+1,1)
|((n,_),false)->(n,0)
|(n,_) ->n
{5..(1<<<n)-1}|>Seq.choose(fun i->if fst({0..n-1}|>Seq.takeWhile(fun n->(1<<<(n-1))<i)|>Seq.fold(fun n g->fn (n,(i&&&(1<<<g)>0)))(0,0)) > 1 then Some(i) else None)
</lang>
Again counting the number of non-continuous subsequences
<pre>
> Seq.length (Nonseq 20);;
Real: 00:00:02.356, CPU: 00:00:02.389, GC gen0: 183, gen1: 0
> Seq.length (Nonseq 23);;
Real: 00:00:20.714, CPU: 00:00:20.950, GC gen0: 1571, gen1: 0
val it : int = 8388331
> Seq.length (Nonseq 24);;
Real: 00:00:43.129, CPU: 00:00:43.601, GC gen0: 3216, gen1: 0
val it : int = 16776915
> Seq.length (Nonseq 25);;
Real: 00:01:28.853, CPU: 00:01:29.869, GC gen0: 6577, gen1: 0
val it : int = 33554106
</pre>
===Conclusion===
Find a better filter or use the generator.
=={{header|Go}}==
Generate the power set (power sequence, actually) with a recursive function, but keep track of the state of the subsequence on the way down. When you get to the bottom, if state == non-continuous, then include the subsequence. It's just filtering merged in with generation.
| |||