Rosetta Code

Non-continuous subsequences: Difference between revisions

Page Discussion

Non-continuous subsequences (view source)

Revision as of 17:47, 20 March 2018

20 bytes added ,  6 years ago
→‎{{header|Julia}}
No edit summary
Line 1,194:
 
=={{header|Julia}}==
{{works with|Julia|0.6}}
 
This solution uses an iterator over non-contiguous sub-sequences, <tt>NCSubSeq</tt>. In the spirit of Julia's <tt>permutations</tt> and <tt>combinations</tt> built-ins, <tt>NCSubSeq</tt> provides an array of indices that can be used to create each subsequence from the full sequence. Sub-sequences are indexed by integers whose bit patterns indicate which members are included.
 
Line 1,201 ⟶ 1,203:
 
'''Iterator and Functions'''
<lang Julia>iscontseq(n::Integer) = count_zeros(n) == leading_zeros(n) + trailing_zeros(n)
<lang Julia>
iscontseq(n::IntegerBigInt) = count_zeros!ismatch(n)r"0", == leading_zerosrstrip(bin(n), + trailing_zeros(n'0'))
iscontseq(n::BigInt) = !ismatch(r"0", rstrip(bin(n), '0'))
 
function makeint2seq(n::Integer)
Line 1,214 ⟶ 1,215:
end
 
immutablestruct NCSubSeq{T<:Integer}
n::T
end
 
typemutable struct NCSubState{T<:Integer}
m::T
m2s::Function
end
 
Base.lengthiteratorsize(a::NCSubSeq) = 2^aBase.n - divHasLength(a.n*(a.n+1), 2) - 1
Base.startlength(a::NCSubSeq) = NCSubState(5,2 ^ a.n - a.n * makeint2seq(a.n + 1)) ÷ 2 - 1
Base.done(a::NCSubSeq, as::NCSubState) = 2^a.n-3 < as.m▼
 
Base.start(a::NCSubSeq) = NCSubState(5, makeint2seq(a.n))
▲Base.done(a::NCSubSeq, as::NCSubState) = 2 ^ a.n - 3 < as.m
function Base.next(a::NCSubSeq, as::NCSubState)
s = as.m2s(as.m)
Line 1,235 ⟶ 1,237:
return (s, as)
end
</lang>▼
 
'''Main'''
<lang Julia>
n = 4
printprintln("Testing NCSubSeq for ", n, " items:\n ", join(NCSubSeq(n), " "))
for a in NCSubSeq(n)▼
print(" ", a)
end
println()
 
s = "Rosetta"
Line 1,250 ⟶ 1,245:
m = 10
n = length(NCSubSeq(length(s))) - m
println("The\nThe first and last ", m, " NC sub-sequences of \"", s, "\":")▼
println()
▲for (i, a) in enumerate(NCSubSeq(nlength(cs)))
▲println("The first and last ", m, " NC sub-sequences of \"", s, "\":")
for (i,a) in enumerate(NCSubSeq(length(cs)))
i <= m || n < i || continue
println(@sprintf "%6d %s" i join(cs[a], ""))
Line 1,259 ⟶ 1,253:
end
 
using IterTools.chain
t = {}
 
append!(t, collect(1:10))
println("Numbers\nThe offirst and last ", m, " NC sub-sequences of a\"", givens, length:"\"")▼
append!(t, collect(20:10:40))
append!for x in IterTools.chain(t1:10, 20:10:40, big.(50):50:200))
println(@sprintf(printf "%7d =>→ %d\n", i),x length(NCSubSeq(i)x))▼
println()
▲end</lang>
▲println("Numbers of NC sub-sequences of a given length:")
for i in t
▲ println(@sprintf("%7d => ", i), length(NCSubSeq(i)))
end
</lang>
 
{{out}}
<pre>Testing NCSubSeq for 4 items:▼
<pre>
[1, 3] [1, 4] [2, 4] [1, 2, 4] [1, 3, 4]▼
▲Testing NCSubSeq for 4 items:
▲ [1,3] [1,4] [2,4] [1,2,4] [1,3,4]
 
The first and last 10 NC sub-sequences of "Rosetta":
Line 1,298 ⟶ 1,287:
99 Rsetta
 
NumbersThe offirst and last 10 NC sub-sequences of a given length:"Rosetta"
1 =>→ 0
2 =>→ 0
3 =>→ 1
4 =>→ 5
5 =>→ 16
6 =>→ 42
7 =>→ 99
8 =>→ 219
9 =>→ 466
10 =>→ 968
20 =>→ 1048365
30 =>→ 1073741358
40 =>→ 1099511626955
50 =>→ 1125899906841348
100 =>→ 1267650600228229401496703200325
150 =>→ 1427247692705959881058285969449495136382735298
200 =>→ 1606938044258990275541962092341162602522202993782792835281275</pre>
</pre>
 
=={{header|Kotlin}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/65404"