Non-continuous subsequences: Difference between revisions
Content added Content deleted
(/* {{header|C++}} * maybe best code/) |
(Realize in F#) |
||
Line 928: | Line 928: | ||
</pre> |
</pre> |
||
=={{header|F_Sharp|F#}}== |
|||
<lang fsharp> |
|||
(* |
|||
A function to generate only the non-continuous subsequences. |
|||
Nigel Galloway July 20th., 2017 |
|||
*) |
|||
let N n = |
|||
let fn n = Seq.map (fun g->(2<<<n)+g) |
|||
let rec fg n = seq{if n>0 then yield! seq{1..((1<<<n)-1)}|>fn n; yield! fg (n-1)|>fn n} |
|||
Seq.collect fg ({1..(n-2)}) |
|||
</lang> |
|||
This may be used as follows: |
|||
<lang fsharp> |
|||
let Ng ng = N ng |> Seq.iter(fun n->printf "%2d -> " n; {0..(ng-1)}|>Seq.iter (fun g->if (n&&&(1<<<g))>0 then printf "%d " (g+1));printfn "") |
|||
Ng 4 |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
5 -> 1 3 |
|||
9 -> 1 4 |
|||
10 -> 2 4 |
|||
11 -> 1 2 4 |
|||
13 -> 1 3 4 |
|||
</pre> |
|||
Counting the number of non-continuous subsequences is interesting: |
|||
<pre> |
|||
> Seq.length (N 4);; |
|||
val it : int = 5 |
|||
> Seq.length (N 10);; |
|||
val it : int = 968 |
|||
> Seq.length (N 23);; |
|||
val it : int = 8388331 |
|||
> Seq.length (N 31);; |
|||
val it : int = 2147483151 |
|||
</pre> |
|||
=={{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. |