Non-continuous subsequences: Difference between revisions
Content added Content deleted
(→{{header|C++}}: we rely on page history for editor and date info as wiki.) |
(jq) |
||
Line 1,035: | Line 1,035: | ||
Outputs: |
Outputs: |
||
<pre>[[1,3],[1,4],[2,4],[1,2,4],[1,3,4]]</pre> |
<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}}== |
=={{header|Mathematica}}== |