How many different unique subsequences are there from a sequence of digits of length N?

Question

Mathematics

There is a sequence of numbers, for example 8 2 4 6 .
This number has 41 subsequences , they are:
8246
246, 846, 826, 824
46, 26, 24, 46, 86, 84, 26, 86, 82, 24, 84, 82
4, 6, 2, 6, 2, 4, 4, 6, 8, 6, 8, 4, 2, 6, 8, 6, 8, 2, 2, 4, 8, 4, 8, 2
With 15 unique :
8246
246, 846, 826, 824
46, 26, 24, 86, 84, 82
4, 6, 2, 8
What algorithm should be used to count the number of unique subsequences?
(Brute force doesn't work. Something more algebraic is needed.)

Answer 1

You can somewhat reduce the number of options when iterating by grouping consecutive identical numbers. Let's say for (1 1 1 2 1 1) we get the original set ((1, 3), (2, 1), (1, 2)). After that, iterate over it recursively.

функция рекурсия(набор, результат) {
    если набор пуст {
        если результат уникален { 
            добавить результат в список уникальных
        }
    }
    ((цифра, количество), следующий_набор) = набор;
    для i от 0 до количество {
        рекурсия(следующий_набор, результат+(цифра i раз));
    }
}
рекурсия(исходный_набор, '');

The first step of the recursion will give the options '', '1', '11' or '111'. The second step adds '' or '2' to each of them. The third step will add '', '1' or '11' to each of the 8 resulting options. That is, instead of 2 ⁶ = 64 options for searching for uniqueness, we get 4 * 2 * 3 = 24.
The more groups of consecutive identical numbers in the initial sequence, the greater the gain. If there are no such groups, then we run into exhaustive enumeration.

Answer 2

In the general case, only exhaustive search is obtained, the number of all subsequences = 2 ⁿ -1

Answer 3

The complete enumeration can be significantly reduced without going through specific permutations of digits: if digits d _i , i = 1...m are chosen, among which there are groups of the same, with the number of digits in each of these groups c _j , j = 1...k, then from these numbers you can make different numbers. This number does not depend on the specifically chosen digits, only on the size of groups of identical digits, i.e. its value can be counted times and cached. It remains to go through all the samples of m digits from the original n, their , and for each of them, by counting the sizes of groups of identical digits, determine how many different numbers can be made.