3

I want to find a Composition of Integer in C and Haskell I find this code for Haskell which works fine:

composition 0 = [[]]
composition n = [x:rest | x <- [1..n], rest <- composition (n-x)]

Sample output of this Code Is:

*Main> composition 3 
[[1,1,1],[1,2],[2,1],[3]]

*Main> composition 4 
[[1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1],[4]]

but I could not develop an equivalent in C: I tried to create recursive function in C but I don't know how to use equivalent of Haskell :[] in C

void composition(int n)
{
        int j;
        if (n==0)
                return;
        for(j=1;j<=n;j++){
                printf ("%d",j);
                composition(n-j);
                printf("\n");
        }

}

sample Output of this code is:

Composition is
111

2

21

3

The correct composition for 3 is

1 1 1
2 1
1 2
3
Geo-7
  • 127
  • 9
  • your question is a little confusing. What exactly are you asking about? C or C# solution? Can you describe for the people who don't know Haskell what the expression: `generate n = [x:rest | x <- [1..n], rest <- generate (n-x)]` does? The more information you provide the easier will it be for the people to answer your question – Mong Zhu Aug 22 '16 at 08:43
  • @LuckAss I add C output – Geo-7 Aug 22 '16 at 08:57
  • @progy_rock 1) I know but I don't know how to fix it 2) I didn't develop it yet, anyway I also and do not know how to create array in a recursive way like I did in Haskel with : colon. – Geo-7 Aug 22 '16 at 09:01
  • 1
    @progy_rock there is sample C# code on stack overflow: http://stackoverflow.com/questions/15048329/finding-all-numbers-that-sum-to-a-specified-target-number-integer-partition but I want a recursive one – Geo-7 Aug 22 '16 at 09:11
  • @progy_rock ok I delete the C# section. – Geo-7 Aug 22 '16 at 09:30

1 Answers1

1

Using printf is not really equivalent : it outputs the result to stdout instead of returning it as list object. In C++ you could do

std::vector<std::vector<int> > composition(int n)
{
    int j;
    if (n == 0)
        return std::vector<std::vector<int> >(0);
    std::vector<std::vector<int> > ret;
    ret.push_back(std::vector<int>(1, n));
    for (j = 1; j <= n; j++) 
    {
        std::vector<std::vector<int> > rec = composition(n - j);
        for (auto& it : rec)
            it.push_back(j);
        ret.insert(ret.begin(), rec.begin(), rec.end());
    }
    return ret;
}

Now if you really want plain C, you have to dynamically allocate the vectors yourself. It is not very fun.

V. Semeria
  • 3,128
  • 1
  • 10
  • 25