Как найти все разделы мультимножества (набор, который позволяет дублировать) - PullRequest
Новая
       8

Как найти все разделы мультимножества (набор, который позволяет дублировать)

0 голосов
/ 05 декабря 2018

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

Например, мультимножество {1, 1, 2} имеет 4 раздела:

раздел 1 = {{1}, {1},{2}} раздел 2 = {{1}, {1, 2}} раздел 3 = {{1, 1}, {2}} раздел 4 = {{1, 1, 2}}

Вот похожий вопрос Как найти все разделы набора , но в этом вопросе все числа различны.

Определение для заданных разделов: https://en.wikipedia.org/wiki/Partition_of_a_set

Определение для мультимножества: https://en.wikipedia.org/wiki/Multiset

Решение, написанное на любом общем языке программирования с некоторыми пояснениями, будет высоко оценено.

Обновление:

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

1 Ответ

0 голосов
/ 05 декабря 2018

Это проблема Набор разделов .

Количество элементов в исходном наборе всегда равно сумме количества элементов в каждом разделе.

Это можно решить с помощью возврата и рекурсии .Эта программа на C ++ может быть полезна. 

void solve (set<vector<vector<int>>>& solution, vector<int> inputSet, 
vector<vector<int>>& partitions, vector<int> partition, int n, int i) {
    int numberOfElements = 0;
    for (int i=0; i<partitions.size(); i++) {
        numberOfElements += partitions[i].size();
    }
    if (numberOfElements == n) {
        vector<vector<int>> newPartitions = partitions;
        for (int i=0; i<newPartitions.size(); i++) {
            sort (newPartitions[i].begin(), newPartitions[i].end());
        }
        sort(newPartitions.begin(), newPartitions.end());
        solution.insert(newPartitions);
        return;  
    }
    for (int j=i; j<n; j++) {
        partition.push_back(inputSet[j]);
        partitions.push_back(partition);
        vector<int> partitionNew;
        solve(solution, inputSet, partitions, partitionNew, n, j+1);
        partitions.pop_back();
    }
}

void permute (set<vector<vector<int>>>& solution, vector<int>& inputSet, int i, int n) {
    if (i == n) {
        vector<int> partition;
        vector<vector<int>> partitions;
        solve(solution, inputSet, partitions, partition, inputSet.size(), 0);
        return;
    }
    for (int j=i; j<=n; j++) {
        swap(inputSet[i], inputSet[j]);
        permute(solution, inputSet, i+1, n);
        swap(inputSet[i], inputSet[j]);
    }
}

Вот рабочий пример: Генерация всех разделов

РЕДАКТИРОВАТЬ: Я неправильно понял вопрос.Я обновил ответ.Теперь генерируются все возможные разделы.

...