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

Question

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;
}

Does this answer your question? [How does this function with a "yield" work in detail?](https://stackoverflow.com/questions/3438670/how-does-this-function-with-a-yield-work-in-detail) — madreflection, Jan 28 '20 at 23:42
This is not what I'd call good C# code (I'm not happy with that for loop at all). Yield return allows a single item in the IEnumerable to be computed at a time. You ought to be able to learn what you need from Microsoft https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/yield — Victor Wilson, Jan 28 '20 at 23:42
Alright, I guess its time to bite the bullet and understand yield in this context. Never thought porting one function to C++ would result in a full days work — raaj, Jan 28 '20 at 23:49
The part that might be most confusing is that the contents don't represent a function, they represent a class. All the internal state of the function ends up in a hidden class which keeps track of where it is in the execution and all the variables. The power of yield return makes it a lot of work to emulate in languages that don't have it. — Bryce Wagner, Jan 28 '20 at 23:56
@raaj check out the [`co_yield`](https://en.cppreference.com/w/cpp/language/coroutines#co_yield) expression, which is part of the C++20 specification. — Patrick Roberts, Jan 29 '20 at 02:59

score -1 · Accepted Answer · answered Jan 29 '20 at 02:56

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.

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

1 Answers1

Linked