Чтобы создать подмножество размера n один за другим, чтобы уменьшить сложность? - PullRequest
Новая
       0

Чтобы создать подмножество размера n один за другим, чтобы уменьшить сложность?

1 голос
/ 17 октября 2011 
void AlgoMMPCbar::subs(const std::vector<unsigned int>& org, const std::vector<unsigned int>& pre, size_t k, size_t n, SubSets& c){
   if (n <= 1) {
    for(size_t i = k; i < org.size(); i++){
        std::vector<unsigned int> v(pre);// instead of printing...
        v.push_back(org.at(i));
        c.push_back(v);
    }
} else {
    size_t n1 = n - 1;
    for(size_t i = k; i != org.size() - n1; i++){   // 
        std::vector<unsigned int> s(pre);
        s.push_back(org.at(i));
        subs(org,s,i+1,n1,c);
    }
}
}
void AlgoMMPCbar::computeSubSets(const std::vector<unsigned int>& org, size_t& n, SubSets& c){
 c.clear(); // clear previous data

std::vector<unsigned int> pre;
pre.reserve(n+1); // for performance
    if (n==0)
      c.push_back(pre);
else
        subs(org,pre,0, n, c); 
}

Приведенный выше код используется для генерации подмножеств размера n для дальнейшей проверки / обработки. Но мне никогда не нужно проверять все эти сгенерированные подмножества (в худшем случае он проверит их все). Основной трудоемкой частью программы является генерация подмножества. Теперь я хочу преобразовать вышеупомянутую функциональность, чтобы генерировать подмножества одно за другим (не все сразу, поэтому я могу остановить дальнейшее генерирование подмножеств в любое время).

Пожалуйста, поделитесь своим опытом, чтобы преобразовать вышеуказанную функциональность в функцию наподобие subset.next (), чтобы сэкономить время вычислений.

Заранее спасибо.

Ответы [ 3 ]

1 голос
/ 17 октября 2011

скажем ind поддерживает индексы для элементов в подмножестве в возрастающем порядке, т.е. 

ind[0] < ind[1] < ... < ind[n-1]

найти наименьшее j такое, что 

j == n-1 || ind[j] + 1 < ind[j+1]

вы можете перейти к следующему подмножеству 

ind[j]++
ind[0] = 0; ind[1] = 1; ... ind[j-1] = j-1

обратите внимание, что новый массив ind все еще отсортирован. Вы можете легко показать, что начиная с 

ind[] = [0, 1, ..., n-1]

вы сгенерируете все подмножества, повторяя описанную выше процедуру. Вы можете получить быстрый код, если будете использовать некоторые приемы для «поддержания» значения j выше, а не для линейного поиска.

0 голосов
/ 17 октября 2011

Я бы создал какой-нибудь вектор состояния и прошел бы через него лексикографически.Поэтому, если у вас есть набор M элементов и вы хотите подмножества размером n, у вас будет вектор n целых чисел, соответствующий выбранным индексам.Затем вы делаете алгоритм next_subset(std::vector<bool> &), который получает следующее подмножество.Например, для подмножеств размера 3 из 5: 

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Я уверен, что вы можете определить шаблон (увеличьте последнее место; если он в конце, переместите его назад и увеличьте два последних места вверх,и т. д.).

Если вы хотите быть немного более эффективным, вы можете сохранить итераторы в исходном контейнере или пары целых чисел и итераторов, если контейнер не имеет произвольного доступа.

0 голосов
/ 17 октября 2011

Ваша функция subs может вернуть bool. В ветке n<=1 вашего if вы можете выполнить соответствующие проверки, и если текущее подмножество совпадает, вы сохраните его и вернете true. В другой ветке вы заменяете вызов subs чем-то вроде if (subs(..)) return true;. И вы добавляете return false в конце. Я понятия не имею, что вам следует делать, если вам потенциально требуется более одного подмножества, и вы точно не знаете, сколько из них подходит.

...