不同子阵列的数目

Question

我想找到一种算法来计算阵列中不同子阵列的数量。

例如，在 A = [1，2，1，2] 的情况下，不同子数组的数量为 7：

{ [1] , [2] , [1,2] , [2,1] , [1,2,1] , [2,1,2], [1,2,1,2]}  

在B=[1,1,1]的情况下，不同子阵列的数量为3:

{ [1] , [1,1] , [1,1,1] }

子数组是数组的连续子序列或片段。不同意味着内容不同；例如:

来自A[0:1]的[1]和来自A[2:3]的[1]不是不同的。

类似地：

B[0：1]，B[1：2]，B[2：3]并不明显。

Answer 1

您可以简单地制作一组子序列并对其进行计数，但我不确定这是最有效的方法，因为它是O（n^2）。

在python中，这将是这样的：

subs = [tuple(A[i:j]) for i in range(0, len(A)) for j in range(i + 1, len(A) + 1)]

uniqSubs = set(subs)

这给了你：

set([(1, 2), (1, 2, 1), (1,), (1, 2, 1, 2), (2,), (2, 1), (2, 1, 2)])

理解中的双循环清楚地说明了O（n²）的复杂性。

显然，有一些关于复杂性的讨论。子项的创建是 O（n^2），因为有 n^2 项。

从列表创建集合是 O（m），其中 m 是列表的大小，在本例中 m 为 n^2，因为添加到集合中是摊销 O（1）。

因此，整体为O（n^2）。

Answer 2

编辑：我想到如何减少迭代/比较次数。我有一种方法可以做到这一点：如果你检索一个大小为n的子数组，那么每个大小小于n的子html" target="_blank">数组都将被添加。

下面是更新后的代码。

    List<Integer> A = new ArrayList<Integer>();
    A.add(1);
    A.add(2);
    A.add(1);
    A.add(2);

    System.out.println("global list to study: " + A);

    //global list
    List<List<Integer>> listOfUniqueList = new ArrayList<List<Integer>>();      

    // iterate on 1st position in list, start at 0
    for (int initialPos=0; initialPos<A.size(); initialPos++) {

        // iterate on liste size, start on full list and then decrease size
        for (int currentListSize=A.size()-initialPos; currentListSize>0; currentListSize--) {

            //initialize current list.
            List<Integer> currentList = new ArrayList<Integer>();

            // iterate on each (corresponding) int of global list
            for ( int i = 0; i<currentListSize; i++) {
                currentList.add(A.get(initialPos+i));
            }

            // insure unicity
            if (!listOfUniqueList.contains(currentList)){
                listOfUniqueList.add(currentList);                      
            } else {
                continue;
            }
        }
    }

System.out.println("list retrieved: " + listOfUniqueList);
System.out.println("size of list retrieved: " + listOfUniqueList.size());

要研究的全球列表： [1， 2， 1， 2]

检索到的列表:[[1，2，1，2]，[1，2，1]，[1，2]，[2，1，2]，[2，1，2]，[2，1]，[2]]

检索到的列表大小:7

如果一个列表多次包含相同的patern，那么迭代和比较的次数将非常少。对于您的示例[1,2,1,2]，如果（！listOfUniqueList.contains（电流列表））{行被执行10次。对于包含15个不同子数组的输入[1,2,1,2,1,2]，它只上升到36。

Answer 3

为此数组构建后缀树。然后把这棵树所有边的长度加在一起。

构造后缀树所需的时间是O（n）与正确的算法（Ukkonen的或McCreight的算法）。遍历树并将长度相加所需的时间也是O（n）。