CODEWITHSUNDEEP
javamath
Ivo
Ivo

Reputation: 23164

How do I get all ways to divide a number in multiple numbers?

I want to divide a number x into y pieces and I want all possible configurations to do this. How can I do this efficiently? Example x=100, y=3. I could do this:

    int x = 100;
    for (int a = 1; a < x; a++) {
        for (int b = a; b < x; b++) {
            for (int c = b; c < x; c++) {
                if (a+b+c == x) {
                    //DO SOMETHING
                }
            }
        }
    }

I think this would work (correct me if I'm wrong) but of course is not very efficient at all because I only want the cases where the if statement is true. And with larger y it takes ages. How could I do this efficiently?

Upvotes: 0

Views: 842

Answers (1)

Serge Ballesta
Serge Ballesta

Reputation: 148890

From your algorithm, I can see that you want x=a+b+c with a<=b<=c.

Obviously for y = 3, we have 1<=a<=x/3, then a<=b<=(x-a)/2, c=x-b-a

For an given y, we get: 1<=a1<=x/y, a1<=a2<=(x-a1)/(y-1), ... ai<=a(i+1)<=(x-a1-...-ai)/(y-i)

But in you want a solution for an arbitrary y, you need a recursive algorithm.

Here is a java implementation:

public void split(int number, int pieces) {
    total = 0;
    dosplit(number, pieces, new ArrayList<Integer>());
}

private void dosplit(int number, int pieces, List<Integer> begin) {
    if (pieces == 1) {
        if (begin.isEmpty() || (number >= begin.get(begin.size() - 1))) {
            begin.add(number);
            total += 1;
            //DO SOMETHING WITH BEGIN
            begin.remove(begin.size() - 1);
        }
    }
    else {
        int start, end;
        start = (begin.isEmpty()) ? 1 : begin.get(begin.size() - 1);
        end = 1 + (1 + number - start)/pieces;
        for(int i=start; i<=end; i++) {
            begin.add(i);
            dosplit(number - i, pieces - 1, begin);
            begin.remove(begin.size() - 1);
        }
    }

split(10,3) correctly yields :

[1, 1, 8]
[1, 2, 7]
[1, 3, 6]
[1, 4, 5]
[2, 2, 6]
[2, 3, 5]
[2, 4, 4]
[3, 3, 4]

with as little useless steps as possible.

But split(504, 18) would yield an unmanageable number or solutions :-(

Upvotes: 1

Related Questions