Я хочу найти алгоритм для подсчета числа различных подмассивов массива.
Например, в случае 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] }
Подматрица представляет собой непрерывную подпоследовательность или срез массива. Различный означает другое содержание; например:
[1] из A [0: 1] и [1] из A [2: 3] не различны.
и аналогичным образом:
B [0: 1], B [1: 2], B [2: 3] не различны.
Построить дерево суффиксов для этого массива. Затем добавьте длины всех ребер в это дерево.
Время, необходимое для построения дерева суффикса, - это O (n) с правильным алгоритмом (алгоритмы Ukkonen или McCreight). Время, необходимое для пересечения дерева и суммирования длин, также равно O (n).
Вы можете тривиально сделать набор подпоследовательностей и подсчитать их, но я не уверен, что это самый эффективный способ, так как это 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).
Изменить: я думаю о том, как уменьшить число итераций/сравнения. Я хочу, чтобы это сделать: если вы получите подматрицу размером n, то все подмассивы размером, меньшим n, уже будут добавлены.
Вот обновленный код.
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], [1], [2, 1, 2], [2, 1], [ 2]]
размер полученного списка: 7
Со списком, содержащим один и тот же patern много раз, число итераций и сравнение будет довольно низким. Для вашего примера [1, 2, 1, 2] строка if (! ListOfUniqueList.contains(currentList)) {выполняется 10 раз. Он только поднимает до 36 для входа [1, 2, 1, 2, 1, 2, 1, 2], который содержит 15 разных подматриц.
Вправо мой первый ответ был немного светлым.
Я предполагаю, что ответ будет состоять в том, чтобы сгенерировать их все, а затем удалить дубликаты. Или, если вы используете язык, подобный Java, с установленным объектом, создайте все массивы и добавьте их в набор int []. Наборы содержат только один экземпляр каждого элемента и автоматически удаляют дубликаты, поэтому вы можете просто получить размер набора в конце
Я могу думать о 2 способах...
сначала вычисляет какой-то хэш, а затем добавляет к множеству. если при добавлении хешей то же самое, это уже существующий массив... затем сделайте подробное сравнение... и запишите его так, чтобы вы знали, что ваш алгоритм хеширования недостаточно хорош...
Во-вторых, нужно использовать какое-то вероятное совпадение, а затем развернуться оттуда... если количество элементов одинаково, а общее количество элементов, добавленных вместе, то же самое, а затем проверить verbosely.
Создайте массив из пары, где каждая пара хранит значение элемента subarray и его индекса.
pair[i] = (A[i],i);
Отсоедините пару в порядке возрастания A[i], а затем уменьшите порядок i.
Рассмотрим пример A = [1,3,6,3,6,3,1,3];
пар после сортировки будет pair = [(1,6),(1,0),(3,7),(3,5),(3,3),(3,1),(6,4),(6,2)]
pair[0] имеет элемент index 6. Из index 6 мы можем иметь два суб-массива [1] и [1,3]. Итак, ANS = 2,
Теперь возьмите каждую последовательную пару один за другим.
Принимая pair[0] и pair[1], pair[1] имеет индекс 0. Мы можем иметь 8 подмассивов, начиная с index 0. Но уже учтены два подмассива [1] и [1,3]. Поэтому, чтобы удалить их, нам нужно сравнить самый длинный общий префикс sub-array для pair[0] и pair[1]. Самая длинная общая длина префикса для индексов, начинающихся с 0 и 6, равна 2 i.e [1,3].
Таким образом, теперь новые четкие подмассивы будут [1,3,6].. to [1,3,6,3,6,3,1,3] т.е. 6 подмассивов.
Таким образом, новое значение ANS равно 2 + 6 = 8;
Итак, для pair[i] и pair[i+1] ANS = ANS + Number of sub-arrays beginning from pair[i+1] - Length of longest common prefix.
Элемент сортировки принимает O (n logn).
Итерация каждой последовательной пары - это O (n), и для каждой итерации наибольший общий префикс принимает O (n), делая всю итерационную часть O (n ^ 2). Это лучшее, что я мог получить.
Вы можете видеть, что для этого нам не нужна пара. Первое значение пары, значение элемента не было обязательным. Я использовал это для лучшего понимания. Вы всегда можете пропустить это.