Non-continuous subsequences: Difference between revisions
jq
(→{{header|C++}}: we rely on page history for editor and date info as wiki.) |
(jq) |
||
Line 1,035:
Outputs:
<pre>[[1,3],[1,4],[2,4],[1,2,4],[1,3,4]]</pre>
=={{header|jq}}==
{{works with|jq|1.4}}
In order to handle arrays of more than a handful of elements, we define
non_continuous_subsequences/0 as a generator; that is, it produces a
stream of arrays, each of which is a non-continuous subsequence of the given sequence.
Since the non-continuous subsequences are dense in the set of all
subsets, we will use the powerset approach, and accordingly begin by
defining subsets/0 as a generator.
<lang jq># Generate a stream of subsets of the input array
def subsets:
if length == 0 then []
else .[0] as $first
| (.[1:] | subsets)
| ., ([$first] + .)
end ;
# Generate a stream of non-continuous indices in the range 0 <= i < .
def non_continuous_indices:
[range(0;.)] | subsets
| select(length > 1 and length != 1 + .[length-1] - .[0]) ;
def non_continuous_subsequences:
(length | non_continuous_indices) as $ix
| [.[ $ix[] ]] ;</lang>
'''Example''':
To show that the above approach can be used for relatively large n, let us count the number of non-continuous subsequences of [0, 1, ..., 19].
<lang jq>def count(f): reduce f as $i (0; . + 1);
count( [range(0;20)] | non_continuous_subsequences)
</lang>
{{out}}
$ jq -n -f powerset_generator.jq
1048365
=={{header|Mathematica}}==
| |||