Devising an algorithm in C for all possible permutations, including zero [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 9 years ago.

Improve this question

I am trying to devise and code an algorithm, in C, to come up with a table listing varying percentages of 5 different components. I need to end up with a table looking something like this:

sugar(50%).....salt(20%)....pepper(10%)....chili(10%)....cayenne(10%) sugar(50%).....salt(50%)....pepper(00%)....chili(00%)....cayenne(00%) sugar(00%).....salt(100%)...pepper(00%)....chili(00%)....cayenne(00%) sugar(10%).....salt(00%)....pepper(90%)....chili(00%)....cayenne(00%)

I need to capture all the possible permutations, and note that 0% is a valid permutation, as can be seen above. The sum of all the permutations must always be 100%.

I realize that to list all the possible permutations with a granularity of 1% would mean a huge number of permutations, so I'd like to be able to pass a variable to my function that would define the level of granularity; the higher the granularity, the lower the number of table entries.

I've looked at many of the questions on SO similar to this, but I could not find one that dealt with situations where 1) the order is not important 2) items could be excluded (in my case, this means an item would have a value of 0); and 3) the example was in C.

[PS: I've simplified things by using food, but this is not homework...see my other posts.]

So, my question is, how can I cod this? I have in fact tried to code this by using a recursive loop:

int variations[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
char names[][10] = { "sugar", "spice", "pepper", "cayenne", "salt", "" );
int componentCount = 5;

for (int i = 0; i < componentCount; ++i)
   for (int j = 1; j < componentCount; ++j)
     for (int k = 2; k < compoentCount; ++k)
        for (int l = 3; l < componentCount; ++l)
          for (int m = 4; m < componentCount; ++m)
              for (int x = 0; x < componentCount; ++x)
                   printf("%s=%d", names[x], variations[x]);

But this doesn't do what I need it to do in terms of capturing all the variations, and I did not post this earlier because I assume I need to take a completely different approach, hence my question: how can this be done?

Answer 1

Let us reformulate it in terms of granularity: what you want is essentially enumerate the ways to express N as a sum of K nonnegative integers. Here, N is the granularity (for 5% increments, N would be 100% / 5% = 20) and K is the number of items.

In such formulation, all it takes is a recursive function with parameters k (index from 0 to K-1) and n (what's left of N), in C-like pseudocode:

int a [MAX_K];

void fun (int k, int n)
{
    int i;
    if (k < 0)
    {
        if (n == 0)
        {
            <print - or otherwise use - array a>
        }
        return;
    }
    for (i = 0; i <= n; i++)
    {
        a[k] = i; // run the branch where k-th item gets i/N of the total sum
        fun (k - 1, n - i);
    }
}

...
<call it as "fun (K - 1, N)">

You can bring a pointer to array a with you in the recursion if a global variable is not an option.

Answer 2

You can solve this problem with recursion. Remember that every recursive function has the following pattern:

• Am I in a simple case? If so, solve the simple problem.
• Am I in a more complicated case? If so, break the problem into one or more simpler problems.
• Solve each simpler problem recursively.
• Now combine the solutions to the simpler problems into a solution to the harder problem.

Always start with the simplest possible problem. What's your simplest problem?

• I have one item which must make up x% of the total.

The solution is: that item makes up x% of the total.

Now suppose you have n items that must make up x% of the total. How do you do it? Break it into simpler problems:

• Suppose item 1 made up 0% of the total. Now I have n-1 items that make up x% of the total. List all the ways of doing that.
• Suppose item 1 made up 5% of the total. Now I have n-1 items that make up x-5% of the total. List all the ways of doing that.
• ...
• Suppose item 1 made up x% of the total. Now I have n-1 items that make up 0% of the total. List all the ways of doing that.

And you're done.

Now translate that into code.

Answer 3

The only sensible way to define the level of granularity is as 1/n, where n is a positive integer. I.e. you want to split up the percentages into multiples of 1/n for some n. Otherwise if you merely want all positive percentages to be greater than 1/n you get infinitely many possibilities. Look up the "stars and bars" construction for how to split up an integer n into k non-negative parts. You will see that the answer for the number of possibilities is (n+k-1 choose k-1) and see how each choice of k-1 numbers from the range 1 to n+k-1 leads to a unique assignment of percentages in the combinations you are trying to generate. There are also references online for how to generate all combinations of a particular size from a set.