Difference between subarray, subset & subsequence

问题:

I'm a bit confused between subarray, subsequence & subset

if I have {1,2,3,4}

then

subsequence can be {1,2,4} OR {2,4} etc. So basically I can omit some elements but keep the order.

subarray would be( say subarray of size 3)

{1,2,3}
{2,3,4} 

Then what would be the subset?

I'm bit confused between these 3.

回答1:

In my opinion, if the given pattern is array, the so called subarray means contiguous subsequence.

For example, if given {1, 2, 3, 4}, subarray can be

{1, 2, 3}
{2, 3, 4}
etc.

While the given pattern is a sequence, subsequence contain elements whose subscripts are increasing in the original sequence.

For example, also {1, 2, 3, 4}, subsequence can be

{1, 3}
{1，4}
etc.

While the given pattern is a set, subset contain any possible combinations of original set.

For example, {1, 2, 3, 4}, subset can be

{1}
{2}
{3}
{4}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
etc.

回答2:

In the context of an array, SubSequence - need not be contigious but needs to maintain the order. But SubArray is contigious and inherently maintains the order.

if you have {1,2,3,4} --- {1,3,4} is a valid SubSequence but its not a subarray.

And subset is no order and no contigious.. So you {1,3,2} is a valid sub set but not a subsequence or subarray.

{1,2} is a valid subarray, subset and subsequence.

All Subarrays are subsequences and all subsequence are subset.

But sometimes subset and subarrays and sub sequences are used interchangably and the word contigious is prefixed to make it more clear.

回答3:

Consider an array:

 {1,2,3,4}

Subarray: contiguous sequence in an array i.e.

{1,2},{1,2,3}

Subsequence: Need not to be contiguous, but maintains order i.e.

{1,2,4}

Subset: Same as subsequence except it has empty set i.e.

 {1,3},{}

Given an array/sequence of size n, possible

Subarray = n*(n+1)/2
Subseqeunce = (2^n) -1 (non-empty subsequences)
Subset = 2^n