How to find all partitions of a set (C++) [duplica

Question

This question already has answers here:

How does this function with a “yield” work in detail? (3 answers)

Closed 6 months ago.

I have the following code in C# that computes partitions of a set

Taken from (How to find all partitions of a set)

public static IEnumerable<List<List<T>>> GetAllPartitions<T>(T[] elements) {
    var lists = new List<List<T>>();
    var indexes = new int[elements.Length];
    lists.Add(new List<T>());
    lists[0].AddRange(elements);
    for (;;) {
        yield return lists;
        int i,index;
        for (i=indexes.Length-1;; --i) {
            if (i<=0)
                yield break;
            index = indexes[i];
            lists[index].RemoveAt(lists[index].Count-1);
            if (lists[index].Count>0)
                break;
            lists.RemoveAt(index);
        }
        ++index;
        if (index >= lists.Count)
            lists.Add(new List<T>());
        for (;i<indexes.Length;++i) {
            indexes[i]=index;
            lists[index].Add(elements[i]);
            index=0;
        }
    }

I am tasked with porting this code to C++. Unfortunately, the yield keyword is throwing me off.

In this section here:

 for (;;) {
        yield return lists; 

What is happening here? The code doesnt work if i remove the yield keyword. This code is also not recursive so I don't know what is happening here

EDIT:

Okay I ported it to C++. Thanks all:

std::vector<std::vector<std::vector<int>>> getPartitions(const std::vector<int>& elements){
    std::vector<std::vector<std::vector<int>>> fList;

    std::vector<std::vector<int>> lists;
    std::vector<int> indexes(elements.size(), 0); // Allocate?
    lists.emplace_back(std::vector<int>());
    lists[0].insert(lists[0].end(), elements.begin(), elements.end());

    int counter = -1;

    for(;;){
        counter += 1;
        fList.emplace_back(lists);

        int i,index;
        bool obreak = false;
        for (i=indexes.size()-1;; --i) {
            if (i<=0){
                obreak = true;
                break;
            }
            index = indexes[i];
            lists[index].erase(lists[index].begin() + lists[index].size()-1);
            if (lists[index].size()>0)
                break;
            lists.erase(lists.begin() + index);
        }
        if(obreak) break;

        ++index;
        if (index >= lists.size())
            lists.emplace_back(std::vector<int>());
        for (;i<indexes.size();++i) {
            indexes[i]=index;
            lists[index].emplace_back(elements[i]);
            index=0;
        }

    }


    return fList;
}

int main()
{
    std::vector<int> elements = {0,1,2,3,4,5};
    auto fLists = getPartitions(elements);

    for(auto& lists : fLists){
        for(auto& l : lists){
            std::cout << "(";
            for(auto& e : l){
                std::cout << e << " ";
            }
            std::cout << ") ";
        }
        std::cout << std::endl;
        std::cout << "--" << std::endl;
    }

    return 0;
}

Answer 1

Long story short, introduce a variable ‘results’ for the returned list of lists, and initialize it at the start of the function. Then translate yield return x into results.Add(x), and translate yield break into return result.

There might be other ways to do it without taking up the memory to store results, but for sure they are difficult. Personally I love the mind-bending qualities of yield return. It is not too easy to explain succinctly but it is somewhat like pausing the executing method while you drop down on the stack to continue executing the calling function. When the calling function requests the next item in the iteration, you resume at the next statement after the yield return. I am sure that compiler people will groan at such an explanation but it works for me.