Non-continuous subsequences: Difference between revisions

=={{header|Picat}}==

This approach uses power_set/1 (from the utils module) to get the proper indices.

<lang Picat>import util.

go =>

println(1..4=non_cont(1..4)),

L = "abcde".reverse(),

println(L=non_cont(L)),

println(ernit=non_cont("ernit")),

println(aaa=non_cont("aaa")),

println(aeiou=non_cont("aeiou")),

nl,

println("Printing just the lengths for 1..N for N = 1..20:"),

foreach(N in 1..20)

println(1..N=non_cont(1..N).length) % just the length

end,

nl.

% get all the non-continuous subsequences

non_cont(L) = [ [L[I] : I in S] : S in non_cont_ixs(L.length)].

% get all the index positions that are non-continuous

non_cont_ixs(N) = [ P: P in power_set(1..N), length(P) > 1, P.last() - P.first() != P.length-1].</lang>

{{out}}

<pre>[1,2,3,4] = [[2,4],[1,4],[1,3],[1,3,4],[1,2,4]]

edcba = [ca,da,db,dba,dca,ea,eb,eba,ec,eca,ecb,ecba,eda,edb,edba,edca]

ernit = [nt,rt,ri,rit,rnt,et,ei,eit,en,ent,eni,enit,ert,eri,erit,ernt]

aaa = [aa]

aeiou = [iu,eu,eo,eou,eiu,au,ao,aou,ai,aiu,aio,aiou,aeu,aeo,aeou,aeiu]

Printing just the lengths for 1..N for N = 1..20:

[1] = 0

[1,2] = 0

[1,2,3] = 1

[1,2,3,4] = 5

[1,2,3,4,5] = 16

[1,2,3,4,5,6] = 42

[1,2,3,4,5,6,7] = 99

[1,2,3,4,5,6,7,8] = 219

[1,2,3,4,5,6,7,8,9] = 466

[1,2,3,4,5,6,7,8,9,10] = 968

[1,2,3,4,5,6,7,8,9,10,11] = 1981

[1,2,3,4,5,6,7,8,9,10,11,12] = 4017

[1,2,3,4,5,6,7,8,9,10,11,12,13] = 8100

[1,2,3,4,5,6,7,8,9,10,11,12,13,14] = 16278

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] = 32647

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] = 65399

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17] = 130918

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] = 261972

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19] = 524097

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] = 1048365</pre>