An algorithm problem about output all subset of all n numbers

Question

Now I'm researching about communications of n cars, the problem I meet can be simplified as:

n numbers, and I want to get all the subsets, which meet the condition that they are divided (like the example below) and all these n numbers are ** all used and used only once**.

Such as if n = 3, I can divide them to:

[[1, 2, 3]]
[[1, 2], [3]]
[[1, 3], [2]]
[[2, 3], [1]]
[[1], [2], [3]]

I've tried to solve it by next_permutation function using c++(because it doesn't have any function for combination problems) but failed because it output too many repeated answers(such as [1 2][3]and [2 1][3], which are actually the same but I don't know how to recognize them)

I think my idea is wrong using this function.

*because it doesn't have any function for combination problems* -- There are plenty of answers on how to use `std::next_permutation` to generate combinations. Did you search for them? — PaulMcKenzie, Apr 02 '23 at 14:19
Thanks for @Parsa 's answer, maybe my expression is not that precise because this problem actually can be divided into 2 parts, the first, getting all the partitions of the n numbers, has been solved by him, and now I'm trying to expand this answer because it doesn't have other valid answers such as it has [1 2 ] [ 3 ] but doesn't have [1 3][ 2 ] — yenaibangbing, Apr 02 '23 at 15:51
See also: https://stackoverflow.com/questions/30893292/generate-all-partitions-of-a-set — beaker, Apr 02 '23 at 17:32

jwezorek · Answer 1 · 2023-04-03T19:11:56.190

You are looking for partitions, not combinations or permutations.

You can find the partitions of a set S with n members by noting that if P(n-1) are the partitions of S-a, where a is an arbitrary member, then you can construct P(n) as the set containing a inserted into each member of P(n-1) in all possible ways. That is, if q is some partition in P(n-1), to construct partitions in P(n), a can be a singleton set appended to q or a can be appended to one of the sets already in q.

Code below:

#include <iostream> 
#include <vector>

using set = std::vector<int>;
using partition = std::vector<set>;
using partitions = std::vector<partition>;

template<typename T>
std::vector<T> append(const std::vector<T>& vec, const T& item) {
    auto output = vec;
    output.push_back(item);
    return output;
}

template<typename T>
std::vector<std::vector<T>> append_to_nth(const std::vector<std::vector<T>>& vec, 
        const T& item, int n) {
    auto output = vec;
    output[n] = append(output[n], item);
    return output;
}

partitions all_partitions(int n) {
    if (n <= 0) {
        return {};
    } else if (n == 1) {
        return { { { 1 } } };
    }
    auto partitions_of_n_minus_1 = all_partitions(n - 1);
    partitions partions_n;
    for (const auto& p : partitions_of_n_minus_1) {
        partions_n.push_back(append(p, set{ n }));
        for (size_t i = 0; i < p.size(); ++i) {
            partions_n.push_back(append_to_nth(p, n, i));
        }
    }
    return partions_n;
}

int main() {
    auto partitions = all_partitions(3);
    for (const auto& partition : partitions) {
        std::cout << "[ ";
        for (const auto& set : partition) {
            std::cout << "[ ";
            for (int item : set) {
                std::cout << item << " ";
            }
            std::cout << "]";
        }
        std::cout << " ]\n";
    }
}

An algorithm problem about output all subset of all n numbers

1 Answers1