Anonymous user
Non-continuous subsequences: Difference between revisions
→{{header|Julia}}: A new entry for Julia
(Nimrod -> Nim) |
(→{{header|Julia}}: A new entry for Julia) |
||
Line 1,110:
$ jq -n -f powerset_generator.jq
1048365
=={{header|Julia}}==
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.
<tt>NCSubSeq</tt> works by filtering indices according to whether all <tt>1</tt>s in these indices have bit pattern that are contiguous (using the <tt>iscontseq</tt> functions). This is an easy to implement approach. Greater efficiency may be achieved by noting that a sequence is contiguous if and only if its index is a difference of two powers of 2. This property is used to create the <tt>length(NCSubSeq(n))</tt> function, which gives the number of sub-sequences of a sequence of length <tt>n</tt>.
<tt>NCSubSeq</tt> works transparently for sequence lengths up to <tt>WORD_SIZE-1</tt> (typically 63). It can be extended to work for longer sequences by casting <tt>n</tt> to a larger integer, e.g. using <tt>Big(n)</tt>. A more polished implementation would handle this extension behind the scenes.
'''Iterator and Functions'''
<lang Julia>
iscontseq(n::Integer) = count_zeros(n) == leading_zeros(n) + trailing_zeros(n)
iscontseq(n::BigInt) = !ismatch(r"0", rstrip(bin(n), '0'))
function makeint2seq(n::Integer)
const idex = collect(1:n)
function int2seq(m::Integer)
d = digits(m, 2, n)
idex[d .== 1]
end
return int2seq
end
immutable NCSubSeq{T<:Integer}
n::T
end
type NCSubState{T<:Integer}
m::T
m2s::Function
end
Base.length(a::NCSubSeq) = 2^a.n - div(a.n*(a.n+1), 2) - 1
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)
as.m += 1
while iscontseq(as.m)
as.m += 1
end
return (s, as)
end
</lang>
'''Main'''
<lang Julia>
n = 4
print("Testing NCSubSeq for ", n, " items:\n ")
for a in NCSubSeq(n)
print(" ", a)
end
println()
s = "Rosetta"
cs = split(s, "")
m = 10
n = length(NCSubSeq(length(s))) - m
println()
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], ""))
i == m || continue
println(" .. ......")
end
t = {}
append!(t, collect(1:10))
append!(t, collect(20:10:40))
append!(t, big(50):50:200)
println()
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:
[1,3] [1,4] [2,4] [1,2,4] [1,3,4]
The first and last 10 NC sub-sequences of "Rosetta":
1 Rs
2 Re
3 oe
4 Roe
5 Rse
6 Rt
7 ot
8 Rot
9 st
10 Rst
.. ......
90 otta
91 Rotta
92 stta
93 Rstta
94 ostta
95 Rostta
96 Retta
97 oetta
98 Roetta
99 Rsetta
Numbers of NC sub-sequences of a given length:
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>
=={{header|Mathematica}}==
| |||