Non-continuous subsequences: Difference between revisions
Content added Content deleted
Line 865: | Line 865: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===Generate only the non-continuous subsequences=== |
|||
<lang fsharp> |
<lang fsharp> |
||
(* |
(* |
||
Line 890: | Line 891: | ||
Counting the number of non-continuous subsequences is interesting: |
Counting the number of non-continuous subsequences is interesting: |
||
<pre> |
<pre> |
||
> Seq.length (N |
> Seq.length (N 20);; |
||
Real: 00:00:00.169, CPU: 00:00:00.169, GC gen0: 0, gen1: 0 |
|||
val it : int = |
val it : int = 1048365 |
||
⚫ | |||
⚫ | |||
> Seq.length (N 23);; |
> Seq.length (N 23);; |
||
Real: 00:00:01.238, CPU: 00:00:01.239, GC gen0: 0, gen1: 0 |
|||
val it : int = 8388331 |
val it : int = 8388331 |
||
> Seq.length (N |
> Seq.length (N 24);; |
||
Real: 00:00:02.520, CPU: 00:00:02.523, GC gen0: 0, gen1: 0 |
|||
val it : int = |
val it : int = 16776915 |
||
⚫ | |||
Real: 00:00:04.926, CPU: 00:00:04.930, GC gen0: 0, gen1: 0 |
|||
val it : int = 33554106 |
|||
</pre> |
</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}}== |
=={{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. |
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. |