Non-continuous subsequences: Difference between revisions
Realize in F#
(/* {{header|C++}} * maybe best code/) |
(Realize in F#) |
||
Line 928:
</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}}==
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.
| |||