Поглядите здесь , если Вы хотите с 7 zip с C#. Это было вопросом в другом сообщении в ТАК. Это могло бы помочь Вам.
Наконец-то! Следуя указаниям в ответе sdcvvc , мы получили его: алгоритм O (n log n) для решения проблемы! Это тоже просто, когда вы это поймете. Те, кто угадал БПФ, были правы.
Проблема: нам дана двоичная строка S
длины n , и мы хотим найти в ней три равномерно расположенных единицы. Например, S
может быть 110110010
, где n = 9. Он равномерно распределил единицы в позициях 2, 5 и 8.
Просканируйте S
слева направо и составьте список L
позиций 1. Для S = 110110010
выше, у нас есть список L = [1, 2, 4, 5, 8]. Этот шаг O (n). Теперь задача состоит в том, чтобы найти арифметическую прогрессию длины 3 в L
, т.е. найти различные a, b, c в L
такие, что ba = cb , или, что эквивалентно a + c = 2b . В приведенном выше примере мы хотим найти прогрессию (2, 5, 8).
Составьте многочлен p
с членами x k для каждого k в L
. В приведенном выше примере мы составляем многочлен p (x) = (x + x 2 + x 4 + x 5 + x ] 8 ) . Это шаг O (n).
Найдите многочлен q
= p 2 , используя быстрое преобразование Фурье . В приведенном выше примере получаем многочлен q (x) = x 16 + 2x 13 + 2x 12 + 3x 10 + 4x 9 + x 8 + 2x 7 + 4x 6 + 2x 5 + x 4 + 2x 3 + x 2 . Этот шаг O (n log n).
Игнорируйте все термины, кроме тех, которые соответствуют x 2k для некоторых k в L
]. Для приведенного выше примера мы получаем члены x 16 , 3x 10 , x 8 , x 4 , x 2 . Этот шаг - O (n), если вы вообще решите это сделать.
Вот ключевой момент: коэффициент при любом x 2b для b в L
равен в точности количеству пар (a, c ) в L
так, что a + c = 2b . [CLRS, Исх. 30.1-7] Одной такой парой всегда является (b, b) (так что коэффициент не меньше 1), но если существует любая другая пара (a, c) , то коэффициент не меньше 3 из (a, c) и (c, a) . В приведенном выше примере коэффициент x 10 равен 3 именно из-за AP (2,5,8). (Эти коэффициенты x 2b всегда будут нечетными числами по указанным выше причинам. И все остальные коэффициенты в q всегда будут четными.)
Итак, тогда, алгоритм состоит в том, чтобы посмотреть на коэффициенты этих членов x 2b и увидеть, не превышает ли какой-либо из них 1. Если их нет, значит, нет равномерно расположенных единиц. Если равно a b в L
, для которого коэффициент перед x 2b больше 1, то мы знаем, что существует пара (a, c) - кроме (b, b) - для которой a + c = 2b . Чтобы найти настоящую пару, мы просто пробуем каждое a в L
(соответствующий c будет 2b-a ) и проверим, есть 1 в позиции 2b-a в S
. Это шаг O (n).
Вот и все, ребята.
Кто-то может спросить: нужно ли нам использовать БПФ? Многие ответы, например бета , flybywire и rsp предполагают, что подход, который проверяет каждую пару единиц и определяет, есть ли 1 в "третьей" позиции, может работать в O (n log n) , основанный на интуиции, что если будет слишком много единиц, мы легко найдем тройку, а если единиц слишком мало, проверка всех пар займет немного времени. К сожалению, хотя эта интуиция верна и простой подход лучше, чем O (n 2 ), он не намного лучше. Как и в ответе sdcvvc , мы можем взять «канторовский набор» строк длиной n = 3 k , с единицами в позициях, троичное представление которых имеет только нули. и двойки (не единицы) в нем. Такая строка имеет 2 k = n (log 2) / (log 3) ≈ n 0. В нем 63 единиц и нет равномерно расположенных единиц, поэтому проверка всех пар будет иметь порядок квадрата количества единиц в нем: это 4 k ≈ n 1.26 , что, к сожалению, асимптотически намного больше, чем (n log n). Фактически, худший случай еще хуже: Лео Мозер в 1953 году построил (эффективно) таких строк, которые содержат n 1-c / √ (log n) единиц в них. но без равномерно расположенных единиц, что означает, что для таких строк простой подход потребует Θ (n 2-2c / √ (log n) ) - только крошечный немного лучше, чем Θ (n 2 ) , что удивительно!
О максимальном количестве единиц в строке длины n без трех равномерно расположенных единиц (которые мы увиденное выше было не менее n 0. 63 из простой конструкции типа Кантора и как минимум n 1-c / √ (log n) с конструкцией Мозера) - это OEIS A003002 . Его также можно вычислить непосредственно из OEIS A065825 как k такое, что A065825 (k) ≤ n
Я подозреваю, что простой подход, который выглядит как O (n ^ 2), на самом деле даст что-то лучшее, например O (n ln (n)). Дольше всего проверяются последовательности (для любого заданного n), которые не содержат троек, и это накладывает серьезные ограничения на количество единиц, которые могут быть в последовательности.
Я придумал кое-что. Размахивая аргументами, но я не смог найти убедительных доказательств. Я собираюсь нанести удар в темноту: ответ - очень умная идея, которую профессор знал так давно, что она кажется очевидной, но для студентов это слишком сложно. (Либо так, либо вы проспали лекцию, посвященную этому.)
Это показалось мне забавной задачей, поэтому я решил попробовать свои силы.
Я предполагаю, что 111000001 найдет первые 3 и будет успешным. По сути, количество нулей, следующих за 1, является важным, поскольку 0111000 совпадает с 111000 согласно вашему определению. Как только вы найдете два случая из 1, следующий найденный 1 завершает трилогию.
Вот он на Python:
def find_three(bstring):
print bstring
dict = {}
lastone = -1
zerocount = 0
for i in range(len(bstring)):
if bstring[i] == '1':
print i, ': 1'
if lastone != -1:
if(zerocount in dict):
dict[zerocount].append(lastone)
if len(dict[zerocount]) == 2:
dict[zerocount].append(i)
return True, dict
else:
dict[zerocount] = [lastone]
lastone = i
zerocount = 0
else:
zerocount = zerocount + 1
#this is really just book keeping, as we have failed at this point
if lastone != -1:
if(zerocount in dict):
dict[zerocount].append(lastone)
else:
dict[zerocount] = [lastone]
return False, dict
Это первая попытка, поэтому я уверен, что это можно было бы написать более аккуратно. Пожалуйста, перечислите ниже случаи, когда этот метод не работает.
Один из способов проникнуть в проблему - подумать о факторах и сдвигах.
При сдвиге вы сравниваете строку единиц и нулей со сдвинутой версией самой себя. Затем вы берете подходящие. Возьмем этот пример со сдвигом на два:
1010101010
1010101010
------------
001010101000
Результирующие единицы (побитовое И) должны представлять все те единицы, которые равномерно разделены двумя. Тот же пример со сдвигом на три:
1010101010
1010101010
-------------
0000000000000
В этом случае нет единиц, которые равномерно разнесены на три друг от друга.
Так что это вам говорит? Хорошо, что вам нужно только проверить сдвиги, которые являются простыми числами. Например, у вас есть две единицы, разделенные шестью. Вам нужно будет протестировать только «две» и «три» смены (поскольку они делят шесть). Например:
10000010
10000010 (Shift by two)
10000010
10000010 (We have a match)
10000010
10000010 (Shift by three)
10000010 (We have a match)
Итак, вам нужно проверить только смены 2,3,5,7,11,13 и т. Д. До простого числа, ближайшего к квадратному корню из размера строки цифр.
Почти решено?
Думаю, я ближе к решению. Обычно:
Я думаю, что самый большой ключ к ответу состоит в том, что самые быстрые алгоритмы сортировки - это O (n * log (n)).
НЕПРАВИЛЬНО
Шаг 1 неверен, как указал коллега. Если у нас есть единицы в положениях 2, 12 и 102. Тогда, взяв модуль 10, все они будут иметь одинаковые остатки, но при этом не разнесены на равные расстояния! Извините.
Хорошо, я собираюсь нанести еще один удар по этой проблеме. Я думаю, что могу доказать алгоритм O (n log (n)), который похож на уже обсуждавшиеся, используя сбалансированное двоичное дерево для хранения расстояний между единицами. Этот подход был вдохновлен наблюдением Джастиса о сведении проблемы к списку расстояний между единицами.
Могли бы мы просканировать входную строку, чтобы построить сбалансированное двоичное дерево вокруг позиции единиц, чтобы каждый узел сохранял положение единицы. и каждое ребро помечено расстоянием до соседнего 1 для каждого дочернего узла. Например:
10010001 gives the following tree
3
/ \
2 / \ 3
/ \
0 7
Это можно сделать за O (n log (n)), поскольку для строки размера n каждая вставка занимает O (log (n)) в худшем случае.
Тогда проблема в для поиска в дереве, чтобы узнать, есть ли на каком-либо узле существует путь от этого узла через левый дочерний элемент, который имеет такое же расстояние, как путь через правого дочернего элемента. Это можно сделать рекурсивно для каждого поддерева. При объединении двух поддеревьев в поиске мы должны сравнить расстояния от путей в левом поддереве с расстояниями от путей в правом. Поскольку количество путей в поддереве будет пропорционально log (n), а количество узлов равно n, я считаю, что это можно сделать за O (n log (n)) времени.
Я что-то пропустил?
Это немного выходит за рамки вопроса, но Майкл Кей имеет отличную статью об использовании XSLT 2 для синтаксического анализа чистого текста в XML.
Я просмотрел код DataGridHeaderBorder (который является границей datagridrowheader), у которого нет собственного шаблона управления, он просто происходит от границы. Помимо программно добавляемых разделителей (разделители представляют собой просто прямоугольники, см. Строку 1199 файла DataGridHeaderBorder.cs), есть индикаторы сортировки. краткий взгляд на код, который у меня был, подсказывает, что они все еще должны быть нарисованы, но они этого не делают, шаг через код в порядке.
Решение состоит в том, чтобы переопределить шаблон управления, я думаю, и добавить их самостоятельно, ссылка на проект кода поможет вам начать работу.
и проверим средний бит, и мы снова нашли равномерно распределенный битЯ понятия не имею, как вычислить сложность для этого, может ли кто-нибудь помочь?
edit: добавить код, чтобы проиллюстрировать мою идею
edit2: попытался скомпилировал мой код и обнаружил несколько серьезных ошибок, исправил
char *binaryStr = "0000010101000100";
int main() {
int head, tail, pos;
head = 0;
tail = strlen(binaryStr)-1;
if( (pos = find3even(head, tail)) >=0 )
printf("found it at position %d\n", pos);
return 0;
}
int find3even(int head, int tail) {
int pos = 0;
if(head >= tail) return -1;
while(binaryStr[head] == '0')
if(head<tail) head++;
while(binaryStr[tail] == '0')
if(head<tail) tail--;
if(head >= tail) return -1;
if( (tail-head)%2 == 0 && //true if odd numbered
(binaryStr[head + (tail-head)/2] == '1') ) {
return head;
}else {
if( (pos = find3even(head, tail-1)) >=0 )
return pos;
if( (pos = find3even(head+1, tail)) >=0 )
return pos;
}
return -1;
}
Я придумал что-то вроде этого:
def IsSymetric(number):
number = number.strip('0')
if len(number) < 3:
return False
if len(number) % 2 == 0:
return IsSymetric(number[1:]) or IsSymetric(number[0:len(number)-2])
else:
if number[len(number)//2] == '1':
return True
return IsSymetric(number[:(len(number)//2)]) or IsSymetric(number[len(number)//2+1:])
return False
Это навеяно andycjw.
Что касается сложности, это может быть O (nlogn), поскольку в каждой рекурсии мы делим на два.
Надеюсь, это поможет.
Я думаю, что нашел способ решения проблемы, но не могу построить формального доказательства. Решение, которое я сделал, написано на Java, и в нем используется счетчик n для подсчета количества обращений к списку / массиву. Таким образом, n должно быть меньше или равно stringLength * log (stringLength), если это правильно. Я попробовал использовать его для чисел от 0 до 2 ^ 22, и он работает.
Он начинается с итерации по входной строке и создания списка всех индексов, содержащих единицу. Это всего лишь O (n).
Затем из списка индексов он выбирает firstIndex и secondIndex, которые больше первого. Эти два индекса должны содержать единицы, потому что они находятся в списке индексов. Отсюда можно рассчитать третий индекс. Если inputString [thirdIndex] равен 1, он останавливается.
public static int testString(String input){
//n is the number of array/list accesses in the algorithm
int n=0;
//Put the indices of all the ones into a list, O(n)
ArrayList<Integer> ones = new ArrayList<Integer>();
for(int i=0;i<input.length();i++){
if(input.charAt(i)=='1'){
ones.add(i);
}
}
//If less than three ones in list, just stop
if(ones.size()<3){
return n;
}
int firstIndex, secondIndex, thirdIndex;
for(int x=0;x<ones.size()-2;x++){
n++;
firstIndex = ones.get(x);
for(int y=x+1; y<ones.size()-1; y++){
n++;
secondIndex = ones.get(y);
thirdIndex = secondIndex*2 - firstIndex;
if(thirdIndex >= input.length()){
break;
}
n++;
if(input.charAt(thirdIndex) == '1'){
//This case is satisfied if it has found three evenly spaced ones
//System.out.println("This one => " + input);
return n;
}
}
}
return n;
}
дополнительное примечание: счетчик n не увеличивается, когда он выполняет итерацию по входной строке для построения списка индексов. Это операция O (n), поэтому она никак не повлияет на сложность алгоритма.
Пока не смог придумать решение :(, но есть некоторые идеи.
Что, если мы начнем с обратной задачи: построить последовательность с максимальным числом единиц и БЕЗ любых равномерно расположенных троек. Если вы можете доказать, что максимальное количество единиц равно o (n), то вы можете улучшить свою оценку, выполняя итерацию только по списку единиц.
Это может помочь ....
Эта проблема сводится к следующему:
Для данной последовательности положительных целых чисел найдите непрерывную подпоследовательность, разделенную на префикс и суффикс, такую, что сумма префикса подпоследовательности равна сумме суффикса подпоследовательности.
Например, для последовательности [3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4]
, мы найдем подпоследовательность [3, 6, 5, 2, 2]
с префиксом [3, 6]
с суммой префикса 9
и суффиксом [5, 2, 2]
с суммой суффикса 9
.
Уменьшение выглядит следующим образом:
Учитывая последовательность нулей и единиц, начиная с крайнего левого, продолжайте движение вправо. Каждый раз, когда встречается еще один, запишите количество ходов с момента обнаружения предыдущего и добавьте это число в результирующую последовательность.
Например, для последовательности [0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0]
, мы найдем сокращение [1, 3, 4]
. Из этого сокращения мы вычисляем непрерывную подпоследовательность [1, 3, 4]
, префикс [1, 3]
с суммой 4
, и суффикс [4]
с суммой 4
.
Это сокращение может быть вычислено в O (n)
.
К сожалению, я не знаю, куда идти дальше.
4] . Из этого сокращения мы вычисляем непрерывную подпоследовательность [1, 3, 4]
, префикс [1, 3]
с суммой 4
, и суффикс [4]
с суммой 4
.
Это сокращение может быть вычислено в O (n)
.
К сожалению, я не знаю, куда идти дальше.
4] . Из этого сокращения мы вычисляем непрерывную подпоследовательность [1, 3, 4]
, префикс [1, 3]
с суммой 4
, и суффикс [4]
с суммой 4
.
Это сокращение может быть вычислено в O (n)
.
К сожалению, я не знаю, куда идти дальше.
Я предполагаю, что причина, по которой это nlog (n), связана со следующим:
Итак, вы иметь n, log (n) и 1 ... O (nlogn)
Изменить: Ой, плохо. Мой мозг установил, что n / 2 было logn ... что, очевидно, не так (удвоение числа элементов по-прежнему удваивает количество итераций во внутреннем цикле). Это все еще n ^ 2, не решая проблему. Ну, по крайней мере, мне нужно написать код :)
Реализация в Tcl
proc get-triplet {input} {
for {set first 0} {$first < [string length $input]-2} {incr first} {
if {[string index $input $first] != 1} {
continue
}
set start [expr {$first + 1}]
set end [expr {1+ $first + (([string length $input] - $first) /2)}]
for {set second $start} {$second < $end} {incr second} {
if {[string index $input $second] != 1} {
continue
}
set last [expr {($second - $first) + $second}]
if {[string index $input $last] == 1} {
return [list $first $second $last]
}
}
}
return {}
}
get-triplet 10101 ;# 0 2 4
get-triplet 10111 ;# 0 2 4
get-triplet 11100000 ;# 0 1 2
get-triplet 0100100100 ;# 1 4 7
При поиске шифрования AES я нашел это у некоторых студентов Стэндфорда. Утверждает, что он самый быстрый. Поддерживает CCM, OCB, GCM и блочное шифрование. )
import java.util.Random;
import junit.framework.TestCase;
public class AlgorithmTest extends TestCase {
/**
* Constructor for GetNumberTest.
*
* @param name The test's name.
*/
public AlgorithmTest(String name) {
super(name);
}
/**
* @see TestCase#setUp()
*/
protected void setUp() throws Exception {
super.setUp();
}
/**
* @see TestCase#tearDown()
*/
protected void tearDown() throws Exception {
super.tearDown();
}
/**
* Tests the algorithm.
*/
public void testEvenlySpacedOnes() {
assertFalse(isEvenlySpaced(1));
assertFalse(isEvenlySpaced(0x058003));
assertTrue(isEvenlySpaced(0x07001));
assertTrue(isEvenlySpaced(0x01007));
assertTrue(isEvenlySpaced(0x101010));
// some fun tests
Random random = new Random();
isEvenlySpaced(random.nextLong());
isEvenlySpaced(random.nextLong());
isEvenlySpaced(random.nextLong());
}
/**
* @param testBits
*/
private boolean isEvenlySpaced(long testBits) {
String testString = Long.toBinaryString(testBits);
char[] ones = testString.toCharArray();
final char ONE = '1';
for (int n = 0; n < ones.length - 1; n++) {
if (ONE == ones[n]) {
for (int m = n + 1; m < ones.length - m + n; m++) {
if (ONE == ones[m] && ONE == ones[m + m - n]) {
System.out.println(" IS evenly spaced: " + testBits + '=' + testString);
System.out.println(" at: " + n + ", " + m + ", " + (m + m - n));
return true;
}
}
}
}
System.out.println("NOT evenly spaced: " + testBits + '=' + testString);
return false;
}
}
Я подумал о подходе «разделяй и властвуй», который мог бы сработать.
Во-первых, при предварительной обработке вам нужно вставить все числа меньше половины вашего входного размера ( n / 3) в список.
Дана строка: 0000010101000100
(обратите внимание, что этот конкретный пример действителен)
Вставьте все простые числа (и 1) от 1 до (16/2) в список: {1 , 2, 3, 4, 5, 6, 7}
Затем разделите его пополам:
100000101 01000100
Продолжайте делать это, пока не дойдете до строк размера 1. Для всех строк размера один с 1 в них добавить индекс строки в список возможностей; в противном случае верните -1 в случае неудачи.
Вам также нужно будет вернуть список все еще возможных интервалов, связанный с каждым начальным индексом. (Начните со списка, который вы создали выше, и удаляйте числа по мере продвижения) Здесь пустой список означает, что вы имеете дело только с одной единицей, и поэтому на этом этапе возможен любой интервал; в противном случае список включает интервалы, которые необходимо исключить.
Итак, продолжая пример выше:
1000 0101 0100 0100
10 00 01 01 01 00 01 00
1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0
На первом этапе комбинирования у нас есть восемь наборов по два. В первом случае у нас есть возможность набора, но мы узнаем, что интервал на 1 невозможен из-за наличия другого нуля. Поэтому мы возвращаем 0 (для индекса) и {2, 3, 4, 5, 7} для того факта, что интервал на 1 невозможен. Во втором у нас ничего нет, поэтому мы возвращаем -1. В третьем случае у нас есть совпадение без исключения пробелов в индексе 5, поэтому возвращаем 5, {1,2,3,4,5,7}. В четвертой паре мы возвращаем 7, {1,2,3,4,5,7}. В пятом верните 9, {1,2,3,4,5,7}. В шестом верните -1. В седьмом верните 13, {1,2,3,4,5,7}. В восьмом верните -1.
Снова объединяя в четыре набора по четыре, мы получаем:
1000
: Return (0, {4,5,6,7})
0101
: возврат (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6,7})
0100
: возврат (9, {3,4,5,6,7})
0100
: Return (13, {3,4,5,6,7})
Объединение в наборы по восемь:
10000101
: Return (0, {5,7} ), (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6,7})
01000100
: Return (9, {4,7}), (13, {3,4,5,6,7})
Объединение в набор из шестнадцати:
10000101 01000100
По мере продвижения мы продолжаем проверять все возможности. До этого шага мы оставили вещи, выходящие за пределы конца строки, но теперь мы можем проверить все возможности.
В основном, мы проверяем первую 1 с интервалами 5 и 7 и обнаруживаем, что они этого не делают. t до единиц. (Обратите внимание, что каждая проверка - ПОСТОЯННАЯ, а не линейное время). Затем мы проверяем вторую (индекс 5) с интервалами 2, 3, 4, 5, 6 и 7 - или мы бы сделали это, но мы можем остановиться на 2, поскольку это действительно совпадает.
Фу! Это довольно длинный алгоритм.
Я не знаю на 100%, если он O (n log n) из-за последнего шага, но все, что там было, определенно O (n log n) , насколько я могу судить. Я вернусь к этому позже и попытаюсь уточнить последний шаг.
РЕДАКТИРОВАТЬ: Изменил мой ответ, чтобы отразить комментарий Велбога. Приносим извинения за ошибку. Я напишу еще и псевдокод позже, когда у меня будет немного больше времени, чтобы снова расшифровать то, что я написал. ; -)
Это не решение, а идея, аналогичная той, о которой думал Алексей
Я играл с созданием последовательностей с максимальным количеством единиц, и все они очень интересно, я получил до 125 цифр и вот первые 3 цифры это найдено, пытаясь вставить как много «1» бит, как это возможно:
Обратите внимание, что все они фракталы (что неудивительно, учитывая ограничения).Возможно, что-то есть в обратном мышлении, возможно, если строка не является фракталом of с характеристикой, тогда у нее должен быть повторяющийся узор?
Благодаря бета-версии за лучший термин для описания этих чисел.
Обновление: Увы, похоже, что шаблон не работает, когда начинается достаточно большая начальная строка, например: 10000000000001:
100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001
Ваша проблема называется СРЕДНИЙ в этой статье (1999):
Задача является 3SUM-сложной, если существует субквадратичное сокращение от задача 3SUM: Для набора A из n целых чисел существуют ли в A элементы a, b, c такие, что a + b + c = 0? Неизвестно, является ли AVERAGE сложным на 3SUM. Однако существует простое линейное сокращение от AVERAGE до 3SUM, описание которого мы опускаем.
Когда целые числа находятся в диапазоне [−u ... u], 3SUM может быть решается за время O (n + u lg u) путем представления S в виде битового вектора и выполнения свертки с использованием БПФ.
Этого достаточно, чтобы решить вашу проблему :).
Что очень важно, так это то, что O (n log n) - это сложность с точки зрения количества нулей и единиц, а не количества единиц (который может быть задан как массив, например [1,5,9,15]). Проверка того, имеет ли набор арифметическую прогрессию, состоящую из единиц, является сложной задачей, и согласно этой статье на 1999 год не известен алгоритм, более быстрый, чем O (n 2 ), и предполагается, что это не так. не существует. Каждый, кто не принимает это во внимание, пытается решить открытую проблему.
Другая интересная информация, в основном несущественная:
Нижняя граница:
Простая нижняя граница - это канторовское множество (числа 1..3 ^ n-1, не содержащее 1 в своем тройном расширении) - его плотность n ^ (log_3 2) (около 0,631). Поэтому любая проверка, не слишком ли большой набор, а затем проверки всех пар недостаточно, чтобы получить O (n log n). Вы должны исследовать последовательность умнее. Лучшая нижняя граница цитируется здесь - это n 1-c / (log (n)) ^ (1/2) . Это означает, что набор Кантора не оптимален.
Верхняя граница - мой старый алгоритм:
Известно, что для больших n подмножество {1,2, ..., n} не содержащая арифметическая прогрессия имеет не более n / (log n) ^ (1/20) элементов. Статья О троек в арифметической прогрессии доказывает больше: набор не может содержать более n * 2 28 * (log log n / log n) 1/2 элементы. Таким образом, вы можете проверить, достигнута ли эта граница, а если нет, наивно проверить пары. Это алгоритм O (n 2 * log log n / log n), более быстрый, чем O (n 2 ). К сожалению "На троек ..." есть на Springer - но первая страница доступна, и изложение Бена Грина доступно здесь , стр. 28, теорема 24.
Между прочим, статьи относятся к 1999 году - в том же году, что и первая. один я упомянул, так что, вероятно, поэтому первый не упоминает этот результат.
Для простого типа проблемы (то есть вы выполняете поиск по трем «1» и только (т.е. ноль или более) «0» между ними). Это довольно просто: вы можете просто разделить последовательность на каждую «1» и искать две соседние подпоследовательности одинаковой длины (вторая подпоследовательность, конечно, не последняя). Очевидно, это можно сделать за O (n) раз.
Для более сложной версии (т.е. вы выполняете поиск по индексу i и пробелу g > 0 такое, что s [i] == s [i + g] == s [i + 2 * g] == "1"
), я не уверен, существует ли раствор O (n log n) , поскольку возможно существует O (n²) триплетов, обладающих этим свойством (представьте себе строку из всех единиц, таких триплетов приблизительно n² / 2 ). Конечно, вы ищете только один из них, но я пока не знаю, как его найти ...
Редакция: 2009-10-17 23:00
Я запускал это на больших числах (например, строках по 20 миллионов), и теперь я считаю, что этот алгоритм не O (n войти). Несмотря на это, это достаточно классная реализация и содержит ряд оптимизаций, благодаря которым она работает очень быстро. Он оценивает все расположения двоичных строк из 24 или менее цифр менее чем за 25 секунд.
Я обновил код, включив в него 0 <= L
Оригинал
По сути, это похоже на , еще один вопрос, на который я ответил . Этот код также просматривает три значения в серии и определяет, удовлетворяет ли триплет условию. Вот адаптированный из этого код C #:
using System;
using System.Collections.Generic;
namespace StackOverflow1560523
{
class Program
{
public struct Pair<T>
{
public T Low, High;
}
static bool FindCandidate(int candidate,
List<int> arr,
List<int> pool,
Pair<int> pair,
ref int iterations)
{
int lower = pair.Low, upper = pair.High;
while ((lower >= 0) && (upper < pool.Count))
{
int lowRange = candidate - arr[pool[lower]];
int highRange = arr[pool[upper]] - candidate;
iterations++;
if (lowRange < highRange)
lower -= 1;
else if (lowRange > highRange)
upper += 1;
else
return true;
}
return false;
}
static List<int> BuildOnesArray(string s)
{
List<int> arr = new List<int>();
for (int i = 0; i < s.Length; i++)
if (s[i] == '1')
arr.Add(i);
return arr;
}
static void BuildIndexes(List<int> arr,
ref List<int> even, ref List<int> odd,
ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
{
for (int i = 0; i < arr.Count; i++)
{
bool isEven = (arr[i] & 1) == 0;
if (isEven)
{
evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
even.Add(i);
}
else
{
oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
odd.Add(i);
}
}
}
static int FindSpacedOnes(string s)
{
// List of indexes of 1s in the string
List<int> arr = BuildOnesArray(s);
//if (s.Length < 3)
// return 0;
// List of indexes to odd indexes in arr
List<int> odd = new List<int>(), even = new List<int>();
// evenIndex has indexes into arr to bracket even numbers
// oddIndex has indexes into arr to bracket odd numbers
List<Pair<int>> evenIndex = new List<Pair<int>>(),
oddIndex = new List<Pair<int>>();
BuildIndexes(arr,
ref even, ref odd,
ref evenIndex, ref oddIndex);
int iterations = 0;
for (int i = 1; i < arr.Count-1; i++)
{
int target = arr[i];
bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) ||
FindCandidate(target, arr, even, evenIndex[i], ref iterations);
if (found)
return iterations;
}
return iterations;
}
static IEnumerable<string> PowerSet(int n)
{
for (long i = (1L << (n-1)); i < (1L << n); i++)
{
yield return Convert.ToString(i, 2).PadLeft(n, '0');
}
}
static void Main(string[] args)
{
for (int i = 5; i < 64; i++)
{
int c = 0;
string hardest_string = "";
foreach (string s in PowerSet(i))
{
int cost = find_spaced_ones(s);
if (cost > c)
{
hardest_string = s;
c = cost;
Console.Write("{0} {1} {2}\r", i, c, hardest_string);
}
}
Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
}
}
}
}
Основные отличия:
Общая идея состоит в том, чтобы работать с индексами, а не с индексами. необработанное представление данных. Вычисление массива, в котором появляются единицы, позволяет алгоритму работать во времени, пропорциональном количеству единиц в данных, а не во времени, пропорциональном длине данных. Это стандартное преобразование: создать структуру данных, которая позволяет работать быстрее, сохраняя при этом эквивалент проблемы.
Результаты устарели: удалено.
Редактировать: 2009-10-16 18:48
На данных yx, которым придают некоторую достоверность в других ответах как репрезентативных точных данных для расчета, я получаю эти результаты ... Я удалил их . Они устарели.
Я хотел бы отметить, что эти данные не самые сложные для моего алгоритма, поэтому я думаю, что предположение, что фракталы yx сложнее всего решить, ошибочно. Я полагаю, что наихудший случай для конкретного алгоритма будет зависеть от самого алгоритма и вряд ли будет согласован для разных алгоритмов.
Редактировать: 2009-10-17 13:30
Дальнейшие наблюдения по этому поводу.
] Сначала преобразуйте строку из нулей и единиц в массив индексов для каждой позиции единиц. Скажем, длина этого массива A равна X. Тогда цель состоит в том, чтобы найти
0 <= L < M < U <= X-1
такое, что
A[M] - A[L] = A[U] - A[M]
или
2*A[M] = A[L] + A[U]
Поскольку сумма A [L] и A [U] дает четное число, они не могут быть (четными, нечетными) или (нечетными, четными). Поиск соответствия можно улучшить, разделив A [] на нечетные и четные пулы и поочередно выполняя поиск совпадений на A [M] в пулах нечетных и четных кандидатов.
Однако это скорее оптимизация производительности. чем алгоритмическое улучшение, я думаю. Количество сравнений должно уменьшиться, но порядок алгоритма должен быть таким же.
Edit 2009-10-18 00:45
Еще одна оптимизация происходит со мной, в том же духе, что и разделение кандидатов на четные и странно. Поскольку три индекса должны складываться с кратным 3 (a, a + x, a + 2x - mod 3 равен 0, независимо от a и x), вы можете разделить L, M и U на их значения mod 3 :
M L U
0 0 0
1 2
2 1
1 0 2
1 1
2 0
2 0 1
1 0
2 2
Фактически, вы можете объединить это с четным / нечетным наблюдением и разделить их на их значения mod 6:
M L U
0 0 0
1 5
2 4
3 3
4 2
5 1
и так далее.
Возможно, вам удастся адаптировать алгоритм Рабина-Карпа. Его сложность равна 0 (n), поэтому он может вам помочь.
Взгляните http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm
Может ли это быть решением? Я не уверен, что это O (nlogn), но, на мой взгляд, это лучше, чем O (n²), потому что единственный способ не найти тройку - это распределение простых чисел.
Есть возможности для улучшения, второй найденный 1 может быть следующим первым 1. Также без проверки ошибок.
#include <iostream>
#include <string>
int findIt(std::string toCheck) {
for (int i=0; i<toCheck.length(); i++) {
if (toCheck[i]=='1') {
std::cout << i << ": " << toCheck[i];
for (int j = i+1; j<toCheck.length(); j++) {
if (toCheck[j]=='1' && toCheck[(i+2*(j-i))] == '1') {
std::cout << ", " << j << ":" << toCheck[j] << ", " << (i+2*(j-i)) << ":" << toCheck[(i+2*(j-i))] << " found" << std::endl;
return 0;
}
}
}
}
return -1;
}
int main (int agrc, char* args[]) {
std::string toCheck("1001011");
findIt(toCheck);
std::cin.get();
return 0;
}
# <algorithm>
def contains_evenly_spaced?(input)
return false if input.size < 3
one_indices = []
input.each_with_index do |digit, index|
next if digit == 0
one_indices << index
end
return false if one_indices.size < 3
previous_indexes = []
one_indices.each do |index|
if !previous_indexes.empty?
previous_indexes.each do |previous_index|
multiple = index - previous_index
success_index = index + multiple
return true if input[success_index] == 1
end
end
previous_indexes << index
end
return false
end
# </algorithm>
def parse_input(input)
input.chars.map { |c| c.to_i }
end
У меня проблемы с наихудший сценарий с миллионами цифр. Фаззинг из / dev / urandom
по существу дает вам O (n), но я знаю, что худший случай еще хуже. Я просто не могу сказать, насколько хуже. Для малых n
тривиально найти входные данные в районе 3 * n * log (n)
, но удивительно трудно отличить их от некоторого другого порядка роста для этой конкретной проблемы.
Может ли кто-нибудь, кто работал с входными данными наихудшего случая, сгенерировать строку длиной больше, скажем, ста тысяч?
Я думаю, что этот алгоритм имеет сложность O (n log n) (C ++, DevStudio 2k5). Я не знаю подробностей того, как анализировать алгоритм, чтобы определить его сложность, поэтому я добавил в код некоторую метрическую информацию для сбора информации. Код подсчитывает количество тестов, выполненных с последовательностью единиц и нулей для любого заданного ввода (надеюсь, я не преуспел в алгоритме). Мы можем сравнить фактическое количество тестов со значением O и посмотреть, есть ли корреляция.
#include <iostream>
using namespace std;
bool HasEvenBits (string &sequence, int &num_compares)
{
bool
has_even_bits = false;
num_compares = 0;
for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i)
{
for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j)
{
++num_compares;
if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1')
{
has_even_bits = true;
// we could 'break' here, but I want to know the worst case scenario so keep going to the end
}
}
}
return has_even_bits;
}
int main ()
{
int
count;
string
input = "111";
for (int i = 3 ; i < 32 ; ++i)
{
HasEvenBits (input, count);
cout << i << ", " << count << endl;
input += "0";
}
}
Эта программа выводит количество тестов для каждой строки длиной до 32 символов. Вот результаты:
n Tests n log (n)
=====================
3 1 1.43
4 2 2.41
5 4 3.49
6 6 4.67
7 9 5.92
8 12 7.22
9 16 8.59
10 20 10.00
11 25 11.46
12 30 12.95
13 36 14.48
14 42 16.05
15 49 17.64
16 56 19.27
17 64 20.92
18 72 22.59
19 81 24.30
20 90 26.02
21 100 27.77
22 110 29.53
23 121 31.32
24 132 33.13
25 144 34.95
26 156 36.79
27 169 38.65
28 182 40.52
29 196 42.41
30 210 44.31
31 225 46.23
Я также добавил значения n log n. Постройте их с помощью выбранного графического инструмента, чтобы увидеть корреляцию между двумя результатами. Распространяется ли этот анализ на все значения n? Не знаю.
Предположение:
Совершенно неверно, говоря о log (n) количестве верхнего предела единиц
РЕДАКТИРОВАТЬ:
Теперь я обнаружил, что с помощью чисел Кантора (если они верны), плотность на множестве равна (2/3) ^ Log_3 (n) (какая странная функция), и я согласен, плотность log (n) / n слишком велика.
Если это верхний предел, существует алгоритм, который решает эту проблему. проблема по крайней мере в O (n * (3/2) ^ (log (n) / log (3))) временной сложности и O ((3/2) ^ (log (n) / log (3))) пространстве сложность. (проверьте ответ Джастиса для алгоритма)
Это все еще намного лучше, чем O (n ^ 2)
Эта функция ((3/2) ^ (log (n) / log (3))) действительно выглядит как n * log (n) на первый взгляд.
Как я получил эту формулу?
Применение числа Кантора к строке.
Предположим, что длина строки 3 ^ p == n
На каждом этапе генерации канторовской строки вы сохраняете 2/3 от предыдущего количества единиц. Примените это p раз.
Это означает (n * ((2/3) ^ p)) -> (((3 ^ p)) * ((2/3) ^ p)) оставшиеся и после упрощения 2 ^ стр.
Это означает 2 ^ p единиц в строке 3 ^ p -> (3/2) ^ p единиц. Подставляем p = log (n) / log (3) и получаем
((3/2) ^ (журнал (n) / журнал (3)))
Ниже представлено решение. Здесь и там могут быть небольшие ошибки, но идея правильная.
Изменить: это не n * log (n)
КОД ПСЕВДО:
foreach character in the string
if the character equals 1 {
if length cache > 0 { //we can skip the first one
foreach location in the cache { //last in first out kind of order
if ((currentlocation + (currentlocation - location)) < length string)
if (string[(currentlocation + (currentlocation - location))] equals 1)
return found evenly spaced string
else
break;
}
}
remember the location of this character in a some sort of cache.
}
return didn't find evenly spaced string
Код C #:
public static Boolean FindThreeEvenlySpacedOnes(String str) {
List<int> cache = new List<int>();
for (var x = 0; x < str.Length; x++) {
if (str[x] == '1') {
if (cache.Count > 0) {
for (var i = cache.Count - 1; i > 0; i--) {
if ((x + (x - cache[i])) >= str.Length)
break;
if (str[(x + (x - cache[i]))] == '1')
return true;
}
}
cache.Add(x);
}
}
return false;
}
Как это работает:
iteration 1:
x
|
101101001
// the location of this 1 is stored in the cache
iteration 2:
x
|
101101001
iteration 3:
a x b
| | |
101101001
//we retrieve location a out of the cache and then based on a
//we calculate b and check if te string contains a 1 on location b
//and of course we store x in the cache because it's a 1
iteration 4:
axb
|||
101101001
a x b
| | |
101101001
iteration 5:
x
|
101101001
iteration 6:
a x b
| | |
101101001
a x b
| | |
101101001
//return found evenly spaced string
Я подумал, что добавлю один комментарий перед тем как выложить 22 наивное решение проблемы. Для наивного решения нам не нужно показывать, что число 1 ' хотя смотрю вперед, а не назад.
Жадный построитель строк:
#assumes final char hasn't been added, and would be a 1
def lastCharMakesSolvable(Str):
endIndex=len(Str)
j=endIndex-1
while j-(endIndex-j) >= 0:
k=j-(endIndex-j)
if k >= 0 and Str[k]=='1' and Str[j]=='1':
return True
j=j-1
return False
def expandString(StartString=''):
if lastCharMakesSolvable(StartString):
return StartString + '0'
return StartString + '1'
n=1
BaseStr=""
lastCount=0
while n<1000000:
BaseStr=expandString(BaseStr)
count=BaseStr.count('1')
if count != lastCount:
print(len(BaseStr), count)
lastCount=count
n=n+1
(В свою защиту, я все еще нахожусь на стадии понимания «изучать питон»)
Кроме того, потенциально полезный результат жадного построения строк, есть довольно последовательный переход после достижение степени 2 в количестве единиц ... чего я не хотел ждать, чтобы засвидетельствовать достижение 2096.
strlength # of 1's
1 1
2 2
4 3
5 4
10 5
14 8
28 9
41 16
82 17
122 32
244 33
365 64
730 65
1094 128
2188 129
3281 256
6562 257
9842 512
19684 513
29525 1024
Я попытаюсь представить математический подход. Это больше начало, чем конец, поэтому мы будем очень признательны за любую помощь, комментарий или даже противоречие. Однако, если этот подход будет доказан - алгоритм будет прямым поиском в строке.
Учитывая фиксированное количество пробелов k
и строку S
, поиск k-интервал-триплет принимает O (n)
- Мы просто проверяем для каждого 0 <= i <= (n-2k)
if S [i] == S [i + k] == S [i + 2k]
. Тест занимает O (1)
, и мы выполняем его nk
раз, где k
- константа, поэтому требуется O (nk) = O ( n)
.
Предположим, что существует обратная пропорция между количеством 1
и максимальным количеством пробелов, которые нам нужно найти. То есть, если имеется много 1
, должен быть триплет, и он должен быть достаточно плотным; Если имеется только несколько 1
, тройка (если есть) может быть довольно редкой. Другими словами, я могу доказать, что если у меня достаточно 1
, такой триплет должен существовать - и чем больше у меня 1
, то должен быть найден более плотный триплет. Это может быть объяснено принципом голубятни - Надеюсь, что подробнее остановлюсь на нем позже.
Скажем, есть верхняя граница k
на возможное количество пробелов, которые мне нужно искать. Сейчас, для каждого 1
, расположенного в S [i]
, нам нужно проверить наличие 1
в S [i-1]
и S [i + 1]
, S [i-2]
и S [i + 2]
, ... S [ik]
и S [i + k]
. Это занимает O ((k ^ 2-k) / 2) = O (k ^ 2)
для каждого 1
в S
- из-за Формула суммирования рядов Гаусса . Обратите внимание, что это отличается от раздела 1 - у меня k
как верхняя граница количества пробелов, а не как постоянное пространство.
Нам нужно доказать O (n * log (n))
. То есть нам нужно показать, что k * (количество единиц)
пропорционально log (n)
.
Если мы сможем это сделать, алгоритм тривиален - для каждого 1
в S
с индексом i
просто ищите 1
с каждой стороны до расстояние k
. Если два были найдены на одинаковом расстоянии, верните i
и k
. Опять же, сложнее всего было бы найти k
и доказать правильность.
Я был бы очень признателен за ваши комментарии здесь - я пытался найти связь между k
и числом из 1
на моей доске, пока безуспешно.
Как насчет простого решения O (n) с пространством O (n ^ 2)? (Используется предположение, что все побитовые операторы работают в O (1).)
Алгоритм в основном работает в четыре этапа:
Этап 1: для каждого бита в исходном числе выясните, насколько далеко они находятся, но рассмотрим только одно направление. (Я рассмотрел все биты в направлении младшего значащего бита.)
Этап 2: Поменять порядок битов на входе;
Этап 3: Повторить этап 1 на обратном входе.
] Этап 4: Сравните результаты Этапа 1 и Этапа 3. Если какие-либо биты расположены на одинаковом расстоянии выше И ниже, мы должны иметь совпадение.
Имейте в виду, что ни один шаг в приведенном выше алгоритме не занимает больше времени, чем O (n). ^ _ ^
В качестве дополнительного преимущества этот алгоритм найдет ВСЕ одинаково расположенные единицы из КАЖДОГО числа. Так, например, если вы получите результат «0x0005» то есть на одинаковом расстоянии друг от друга, ОБЕИ на 1 и 3 единицы
Я действительно не пытался оптимизировать приведенный ниже код, но это компилируемый код C #, который, кажется, работает.
using System;
namespace ThreeNumbers
{
class Program
{
const int uint32Length = 32;
static void Main(string[] args)
{
Console.Write("Please enter your integer: ");
uint input = UInt32.Parse(Console.ReadLine());
uint[] distancesLower = Distances(input);
uint[] distancesHigher = Distances(Reverse(input));
PrintHits(input, distancesLower, distancesHigher);
}
/// <summary>
/// Returns an array showing how far the ones away from each bit in the input. Only
/// considers ones at lower signifcant bits. Index 0 represents the least significant bit
/// in the input. Index 1 represents the second least significant bit in the input and so
/// on. If a one is 3 away from the bit in question, then the third least significant bit
/// of the value will be sit.
///
/// As programed this algorithm needs: O(n) time, and O(n*log(n)) space.
/// (Where n is the number of bits in the input.)
/// </summary>
public static uint[] Distances(uint input)
{
uint[] distanceToOnes = new uint[uint32Length];
uint result = 0;
//Sets how far each bit is from other ones. Going in the direction of LSB to MSB
for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
{
distanceToOnes[arrayIndex] = result;
result <<= 1;
if ((input & bitIndex) != 0)
{
result |= 1;
}
}
return distanceToOnes;
}
/// <summary>
/// Reverses the bits in the input.
///
/// As programmed this algorithm needs O(n) time and O(n) space.
/// (Where n is the number of bits in the input.)
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static uint Reverse(uint input)
{
uint reversedInput = 0;
for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1)
{
reversedInput <<= 1;
reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0);
}
return reversedInput;
}
/// <summary>
/// Goes through each bit in the input, to check if there are any bits equally far away in
/// the distancesLower and distancesHigher
/// </summary>
public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher)
{
const int offset = uint32Length - 1;
for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
{
//hits checks if any bits are equally spaced away from our current value
bool isBitSet = (input & bitIndex) != 0;
uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex];
if (isBitSet && (hits != 0))
{
Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits));
}
}
}
}
}
Кто-то, вероятно, прокомментирует это для любого достаточно большого число, побитовые операции не могут выполняться в O (1). Вы были бы правы. Однако я бы предположил, что каждое решение, использующее сложение, вычитание, умножение или деление (что не может быть выполнено путем сдвига), также будет иметь эту проблему.
Очевидно, что нам нужно хотя бы проверять группы триплетов одновременно, поэтому нам нужно как-то сжать проверки. У меня есть алгоритм-кандидат, но анализ временной сложности выходит за рамки моих возможностей * временного порога.
Постройте дерево, в котором каждый узел имеет трех дочерних элементов, а каждый узел содержит общее количество единиц на его листьях. Также создайте связанный список из единиц. Назначьте каждому узлу допустимую стоимость, пропорциональную охватываемому им диапазону. Пока время, которое мы проводим на каждом узле, находится в рамках бюджета, у нас будет алгоритм O (n lg n).
-
Начнем с корня. Если квадрат общего числа единиц ниже его меньше допустимой стоимости, примените наивный алгоритм. В противном случае выполните рекурсию для его дочерних элементов.
Теперь мы либо вернули в рамках бюджета, либо или мы знаем, что не существует действительных троек, полностью содержащихся в одном из дочерних элементов. Поэтому мы должны проверять триплеты между узлами.
Теперь все становится невероятно запутанным. По сути, мы хотим вернуться к потенциальным наборам потомков, ограничивая диапазон. Как только диапазон ограничен настолько, что наивный алгоритм будет работать в рамках бюджета, вы это сделаете. Наслаждайтесь реализацией этого, потому что я гарантирую, что это будет утомительно. Примеров примерно дюжина случаев.
-
Я думаю, что этот алгоритм будет работать, потому что последовательности без действительных триплетов, кажется, чередуются между группами единиц и множеством нулей. Он эффективно разделяет близлежащее пространство поиска, и дерево имитирует это разбиение.
Время выполнения алгоритма совсем не очевидно. Он полагается на нетривиальные свойства последовательности. Если 1 ' s действительно редки, тогда наивный алгоритм будет работать в рамках бюджета. Если единицы плотные, то совпадение должно быть найдено сразу. Но если плотность «в самый раз» (например, около ~ n ^ 0,63, чего можно добиться, установив все биты в позиции без цифры «2» в базе 3), я не знаю, сработает ли это. Вам нужно будет доказать, что эффект расщепления достаточно силен.
При сканировании единиц добавьте их позиции в список. Добавляя вторую и последующие единицы, сравните их с каждой позицией в списке. Интервал равен currentOne (в центре) - previousOne (слева). Правый бит - currentOne + интервал. Если 1, то конец.
Список единиц растет обратно пропорционально расстоянию между ними. Проще говоря, если у вас много нулей между единицами (как в худшем случае), ваш список известных единиц будет расти довольно медленно.
using System;
using System.Collections.Generic;
namespace spacedOnes
{
class Program
{
static int[] _bits = new int[8] {128, 64, 32, 16, 8, 4, 2, 1};
static void Main(string[] args)
{
var bytes = new byte[4];
var r = new Random();
r.NextBytes(bytes);
foreach (var b in bytes) {
Console.Write(getByteString(b));
}
Console.WriteLine();
var bitCount = bytes.Length * 8;
var done = false;
var onePositions = new List<int>();
for (var i = 0; i < bitCount; i++)
{
if (isOne(bytes, i)) {
if (onePositions.Count > 0) {
foreach (var knownOne in onePositions) {
var spacing = i - knownOne;
var k = i + spacing;
if (k < bitCount && isOne(bytes, k)) {
Console.WriteLine("^".PadLeft(knownOne + 1) + "^".PadLeft(spacing) + "^".PadLeft(spacing));
done = true;
break;
}
}
}
if (done) {
break;
}
onePositions.Add(i);
}
}
Console.ReadKey();
}
static String getByteString(byte b) {
var s = new char[8];
for (var i=0; i<s.Length; i++) {
s[i] = ((b & _bits[i]) > 0 ? '1' : '0');
}
return new String(s);
}
static bool isOne(byte[] bytes, int i)
{
var byteIndex = i / 8;
var bitIndex = i % 8;
return (bytes[byteIndex] & _bits[bitIndex]) > 0;
}
}
}
Вот некоторые мысли, которые, несмотря на все мои усилия, похоже, не завершатся поклоном. Тем не менее, они могут быть полезной отправной точкой для чьего-то анализа.
Рассмотрим предлагаемое решение следующим образом, что является подходом, предложенным несколькими людьми, включая меня в предыдущей версии этого ответа. :)
k=2 n= 3 p= 1 101
k=3 n= 6 p= 3 101001
k=4 n=10 p= 6 1010010001
k=5 n=15 p=10 101001000100001
k=6 n=21 p=15 101001000100001000001
Связь между n и p такова, что n = p + k.
Процесс прохождения строки занимает O (n) времени. Каждый раз, когда встречается 1, выполняется максимум (k-1) сравнений. Поскольку n = k (k + 1) / 2, n> k ** 2, поэтому sqrt (n)> k. Это дает нам O (n sqrt (n)) или O (n ** 3/2). Однако обратите внимание, что это может быть не очень жесткая граница, потому что количество сравнений идет от 1 до максимального k, а не k все время. Но я' m не знаю, как учесть это в математике.
Это все еще не O (n log (n)). Кроме того, я не могу доказать, что это наихудший случай, хотя я подозреваю, что это так. Я думаю, что более плотная упаковка единиц впереди приводит к еще более разреженной упаковке в конце.
Поскольку кто-то все еще может счесть это полезным, вот мой код для этого решения на Perl:
#!/usr/bin/perl
# read input as first argument
my $s = $ARGV[0];
# validate the input
$s =~ /^[01]+$/ or die "invalid input string\n";
# strip leading and trailing 0's
$s =~ s/^0+//;
$s =~ s/0+$//;
# prime the position list with the first '1' at position 0
my @p = (0);
# start at position 1, which is the second character
my $i = 1;
print "the string is $s\n\n";
while ($i < length($s)) {
if (substr($s, $i, 1) eq '1') {
print "found '1' at position $i\n";
my @t = ();
# assuming this is the middle '1', go through the positions
# of all the prior '1's and check whether there's another '1'
# in the correct position after this '1' to make a solution
while (scalar @p) {
# $p is the position of the prior '1'
my $p = shift @p;
# $j is the corresponding position for the following '1'
my $j = 2 * $i - $p;
# if $j is off the end of the string then we don't need to
# check $p anymore
next if ($j >= length($s));
print "checking positions $p, $i, $j\n";
if (substr($s, $j, 1) eq '1') {
print "\nsolution found at positions $p, $i, $j\n";
exit 0;
}
# if $j isn't off the end of the string, keep $p for next time
push @t, $p;
}
@p = @t;
# add this '1' to the list of '1' positions
push @p, $i;
}
$i++;
}
print "\nno solution found\n";
Здесь нет теоретического ответа, но я написал быструю программу на Java для исследования поведения во время работы как функции от k и n, где n - общая длина в битах, а k - количество 1-е. Я согласен с несколькими респондентами, которые утверждают, что "обычный" алгоритм, который проверяет все пары битовых позиций и ищет третий бит, даже если для этого потребуется O (k ^ 2) в худшем случае, в В действительности, поскольку в худшем случае нужны разреженные битовые строки, это O (n ln n).
В любом случае, вот программа, ниже. Это программа в стиле Монте-Карло, которая запускает большое количество испытаний NTRIALS для константы n и случайным образом генерирует битовые наборы для диапазона k-значений с использованием процессов Бернулли с ограничением плотности единиц в пределах, которые могут быть указаны, и записывает время выполнения поиска или невозможности найти триплет равномерно распределенных, время измеряется шагами, а НЕ временем ЦП. Я запустил его для n = 64, 256, 1024, 4096, 16384 * (все еще работает), сначала тестовый прогон с 500000 попыток, чтобы увидеть, какие k-значения занимают наибольшее время работы, затем еще один тест с 5000000 попытками с суженными - фокус плотности, чтобы увидеть, как выглядят эти значения. Наибольшее время работы случается с очень разреженной плотностью (например, для n = 4096 пики времени работы находятся в диапазоне k = 16-64, с плавным пиком для среднего времени выполнения на 4212 шагов @ k = 31, максимальное время выполнения достигает пика на 5101 шаги @ k = 58). Похоже, что для наихудшего шага O (k ^ 2) потребуются чрезвычайно большие значения N, чтобы он стал больше, чем шаг O (n), на котором вы сканируете битовую строку, чтобы найти индексы позиции 1.
package com.example.math;
import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;
public class EvenlySpacedOnesTest {
static public class StatisticalSummary
{
private int n=0;
private double min=Double.POSITIVE_INFINITY;
private double max=Double.NEGATIVE_INFINITY;
private double mean=0;
private double S=0;
public StatisticalSummary() {}
public void add(double x) {
min = Math.min(min, x);
max = Math.max(max, x);
++n;
double newMean = mean + (x-mean)/n;
S += (x-newMean)*(x-mean);
// this algorithm for mean,std dev based on Knuth TAOCP vol 2
mean = newMean;
}
public double getMax() { return (n>0)?max:Double.NaN; }
public double getMin() { return (n>0)?min:Double.NaN; }
public int getCount() { return n; }
public double getMean() { return (n>0)?mean:Double.NaN; }
public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; }
// some may quibble and use n-1 for sample std dev vs population std dev
public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
for (int i = 0; i < statistics.length; ++i)
{
StatisticalSummary summary = statistics[i];
ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
i,
summary.getCount(),
summary.getMin(),
summary.getMax(),
summary.getMean(),
summary.getStdDev());
}
}
}
public interface RandomBernoulliProcess // see http://en.wikipedia.org/wiki/Bernoulli_process
{
public void setProbability(double d);
public boolean getNextBoolean();
}
static public class Bernoulli implements RandomBernoulliProcess
{
final private Random r = new Random();
private double p = 0.5;
public boolean getNextBoolean() { return r.nextDouble() < p; }
public void setProbability(double d) { p = d; }
}
static public class TestResult {
final public int k;
final public int nsteps;
public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; }
}
////////////
final private int n;
final private int ntrials;
final private double pmin;
final private double pmax;
final private Random random = new Random();
final private Bernoulli bernoulli = new Bernoulli();
final private BitSet bits;
public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
this.bits = new BitSet(n);
}
/*
* generate random bit string
*/
private int generateBits()
{
int k = 0; // # of 1's
for (int i = 0; i < n; ++i)
{
boolean b = bernoulli.getNextBoolean();
this.bits.set(i, b);
if (b) ++k;
}
return k;
}
private int findEvenlySpacedOnes(int k, int[] pos)
{
int[] bitPosition = new int[k];
for (int i = 0, j = 0; i < n; ++i)
{
if (this.bits.get(i))
{
bitPosition[j++] = i;
}
}
int nsteps = n; // first, it takes N operations to find the bit positions.
boolean found = false;
if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
{
int lastBitSetPosition = bitPosition[k-1];
for (int j1 = 0; !found && j1 < k; ++j1)
{
pos[0] = bitPosition[j1];
for (int j2 = j1+1; !found && j2 < k; ++j2)
{
pos[1] = bitPosition[j2];
++nsteps;
pos[2] = 2*pos[1]-pos[0];
// calculate 3rd bit index that might be set;
// the other two indices point to bits that are set
if (pos[2] > lastBitSetPosition)
break;
// loop inner loop until we go out of bounds
found = this.bits.get(pos[2]);
// we're done if we find a third 1!
}
}
}
if (!found)
pos[0]=-1;
return nsteps;
}
/*
* run an algorithm that finds evenly spaced ones and returns # of steps.
*/
public TestResult run()
{
bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
// probability of bernoulli process is randomly distributed between pmin and pmax
// generate bit string.
int k = generateBits();
int[] pos = new int[3];
int nsteps = findEvenlySpacedOnes(k, pos);
return new TestResult(k, nsteps);
}
public static void main(String[] args)
{
int n;
int ntrials;
double pmin = 0, pmax = 1;
try {
n = Integer.parseInt(args[0]);
ntrials = Integer.parseInt(args[1]);
if (args.length >= 3)
pmin = Double.parseDouble(args[2]);
if (args.length >= 4)
pmax = Double.parseDouble(args[3]);
}
catch (Exception e)
{
System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
System.exit(0);
return; // make the compiler happy
}
final StatisticalSummary[] statistics;
statistics=new StatisticalSummary[n+1];
for (int i = 0; i <= n; ++i)
{
statistics[i] = new StatisticalSummary();
}
EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
int printInterval=100000;
int nextPrint = printInterval;
for (int i = 0; i < ntrials; ++i)
{
TestResult result = test.run();
statistics[result.k].add(result.nsteps);
if (i == nextPrint)
{
System.err.println(i);
nextPrint += printInterval;
}
}
StatisticalSummary.printOut(System.out, statistics);
}
}