Алгоритм подсчета подмножеств

Question

У меня есть следующая проблема, которую я хочу эффективно решить.Мне дают набор из k-кортежей логических значений, где я заранее знаю, что некоторая доля каждого из значений в каждом из k-кортежей является истинной.Например, у меня могут быть следующие 4 кортежа, где каждый кортеж имеет по крайней мере 60% своих логических значений, установленных в true:

(1, 0, 1, 0)
(1, 1, 0, 1)
(0, 0, 1, 0)

Я заинтересован в поиске наборов индексов, которые имеют определенное свойство: если я посмотрю на каждое из значений в кортежах по указанным индексам, то по крайней мере для данной части этих кортежей будет установлен соответствующий бит.Например, в приведенном выше наборе из 4 кортежей я мог бы рассмотреть набор {0}, поскольку, если вы посмотрите на нулевой элемент каждого из вышеперечисленных кортежей, две трети из них равны 1 и 2/3 ~ =66%> 60%.Я мог бы также рассмотреть набор {2} по той же причине.Однако я не мог рассмотреть {1}, так как по индексу 1 только треть кортежей имеет 1, а 1/3 - менее 60%.Точно так же я не мог использовать {0, 2} в качестве набора, потому что это неправда, что как минимум в 60% кортежей установлены биты 0 и 2.

Моя цель - найти все наборы длякоторый имеет это свойство.У кого-нибудь есть хороший алгоритм для решения этой проблемы?

Спасибо.

Answer 1

Как вы уже писали, можно предположить, что архитектура x86_64, и вы ищете производительность реализации, вызывая асимптотическую сложность (так как она не собирается идти под линейной - по определению проблемы;)), я предлагаю следующееалгоритм ( C ++ как псевдокод ):

/* N=16 -> int16; N=8 -> int8 etc. Select N according to input sizes. (maybe N=24 ;) ) */
count_occurences_intN(vector<intN> t, vector<long> &result_counters){
   intN counters[2^N]={};
   //first, count bit combinations
   for_each(v in t)
       ++counters[v];
   //second, count bit occurrences, using aggregated data 
   for(column=0; column<N; ++column){
      mask = 1 << column;
      long *result_counter_ptr = &(result_counters[column]);
      for(v=0; v<2^16; ++v)
         if( v & mask )
            ++(*result_counter_ptr);
   }
}

Чем разделить ваши входные k-битные векторы на N-битные векторы и применить вышеуказанную функцию.В качестве размера ввода вы можете улучшить производительность, выбрав N = 8, N = 16, N = 24 или применив наивный подход.

Как вы уже писали, вы не можете предполагать что-либо на стороне клиента, просто реализуйте N = {8,16,24} и наивно и выберите одну из четырех реализаций в зависимости от размера ввода.

Answer 2

Создайте k-вектор целых чисел, описывающий, сколько проходов было для каждого индекса. Переберите ваш набор, для каждого элемента, увеличивающего k-вектор проходов.

Затем определите количество элементов вашего набора (либо в отдельном цикле, либо в приведенном выше). Затем выполните цикл по вашему вектору отсчетов и сгенерируйте вектор прохождения / неудачи на основе ваших критериев.