Subsequences output missing an element?

Questions
1

Hi

When I search for the Subsequences of {a,b,c,d,e,f}, Mathematica 12 does not return me {a,d,b} which would be a potential solution according to Wikipedia Subsequence - Wikipedia

Maybe the definitions are different ? However, the following site (https://mathworld.wolfram.com/Subsequence.html) seems to confirm that of Wikipedia, with 1<=k<=3 , n1 = 1, n2 = 2 and n3 = 4.

However, Mathematica’s Subsets function seems to return all the expected results…

thanks to clarify that for me

Open in Wolfram Cloud ↗

Subsequences_Subsets.nb (8.56 KB)

2

It seems that Mathematica uses a different definition of subsequence, that corresponds to what Wikipedia calls substring. Subsets corresponds to Wikipedia’s subsequence.

3

Subsequences and Subsets returns combinations, not permutations. Try this:

x = Select[Subsets[{a, b, c, d, e, f}], Length@# == 3 &] ;
Cases[Flatten[Map[Permutations, x], 1], {a, _, _}]

adb.png
adb.png383×142 4.85 KB

4

I actually think the original post had an error. I think the poster expected {a,b,d} to be in the list of subsequences.

5

Hans,

No need for the Select

Subsets[{a, b, c, d, e, f}, {3}]
6

Yes Rohit, you are right.

7

Makes sense. Looks like there might be a problem with Mathematicas Subsequence function.

8

Well, at the very least I think the MathWorld entry is wrong when it says “Subsequence generation is implemented in the Wolfram Language as Subsequences.” I’ve sent a message to the MathWorld team to that effect.

But one can see how this presents a legitimately challenging choice for Wolfram Language. WL has no built-in stucture like a set (where order is literally absent). The typical approach is for List to be used to represent a set, and so, whether it’s relevant to one’s use case or not, the ordering is there. I believe that Subsets was implemented earlier than Subsequences. At the time, the name “Subset” probably made sense. All you need to do if you’re really looking for true subSETS is just ignore the ordering. Furthermore, if Subset guaranteed order preservation, then you’ve killed two birds with one stone, because Subsets will give you the MathWorld definition of subsequences. So, Subsets is a nice and potent function.

But then they wanted to implement a function that produced the contiguous subsequences. What should they name it? “Subsequences” seems appropriate. The MathWorld definition notwithstanding, I think most computer science folks (and probably most non-mathematicians of any type) would interpret “subsequence” to mean contiguous subsequence.

What I would like is an explicit guarantee from Subsets that it preserves order, because if we can assume that, then I think the slight shift in nomenclature is not much of an impediment.