1

What must be efficient algorithm for the given problem statement? (java preferred)

Find a set S of N numbers such that their sum is equal to M. Each number in the set S must fall within the given deviation 'D' from the average M/N.

int M= 100;
int N= 10;
int D= 3;

Here average of M/N = 10. So with deviation of 3, N can be one of the numbers from {7,8,9,10,11,12,13}

Result must be similar to this set:

11 11 9 8 11 9 11 11 9 10

Below the is the program, I came up so far:

    public class RandomNumberGenerator {

    public static void main(String args[]) {
        Random r = new Random();
        int sum = 100;
        int numbers = 10;
        int deviation = 3;

        int iterator = 0;
        int sumTemp = 0;
        int storeArray[] = new int[numbers];
        int average = Math.round((float) sum / (float) numbers);
        int numberOfAttempts = 0;
        int discardedBecauseGreater = 0;
        System.out.println("Average is " + average);

        while (iterator < numbers) {
            int temp = r.nextInt(average + deviation);
            if (temp > average - deviation) {
                storeArray[iterator] = temp;
                sumTemp += temp;
                iterator++;
            }
            if (iterator == numbers) {
                if (sumTemp == sum) {
                    System.out.println("Got the result " + sumTemp);
                    System.out
                            .println("Number of attempts " + numberOfAttempts);
                    System.out.println("Discarded because of greater "
                            + discardedBecauseGreater);
                    for (int i = 0; i < numbers; i++) {
                        System.out.println(storeArray[i]);
                    }

                    break;
                } else {
                    numberOfAttempts++;
                    sumTemp = 0;
                    iterator = 0;
                }
            }

            if (sumTemp > sum) {
                discardedBecauseGreater++;
                sumTemp = 0;
                iterator = 0;
            }

        }
    }
}
Severin Pappadeux
  • 18,636
  • 3
  • 38
  • 64
Balaji Vignesh
  • 446
  • 1
  • 7
  • 19
  • Possible duplicate of [Finding all possible combinations of numbers to reach a given sum](https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum) – hiropon Nov 07 '17 at 10:19
  • FYI http://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/ – hiropon Nov 07 '17 at 10:20
  • 1
    With current formulation `{10,10,10,10,..}` is the simplest solution. – MBo Nov 07 '17 at 10:38
  • @JohnColeman It isn't subset sum (which I'm assuming is the NP-complete problem you're referring to) because you get to come up with the numbers yourself within some range, not pick them from a set, although the problem doesn't appear to be well-specified enough to answer at this stage. – Bernhard Barker Nov 07 '17 at 11:53

2 Answers2

0

Ok, lets reformulated the problem: Sample N values Xi so that:

  • SumiN Xi = 1
  • With mean E[Xi] = 1/N
  • Each Xi fit within +-d from mean

If you're able to sample such numbers, then you could re-scale it to whatever M you want.

What is described here looks like Dirichlet distribution with somewhat large parameters. Suppose we use Dirichlet distribution with all αi equal to the same value a. Following link above:

  • αi = a
  • α0 = N*a
  • E[Xi] = αi/α0 = a / (Na) = 1/N
  • Var[Xi] ~ αi/α02 = 1/(N2a)

So if a is large enough, variance would be very small. Take a look at upper right picture at the link with (7,7,7) case. For final tuning we might use acceptance/rejection - if any value is more that d way, we throw it out and resample.

Code (some presudocode, actually, my Java is rusty). For sampling from Dirichlet distribution, I'm using well-known approach https://stats.stackexchange.com/questions/69210/drawing-from-dirichlet-distribution, with Gamma distribution for Java assuming to come from Apache Common library https://commons.apache.org/proper/commons-math/javadocs/api-3.1/org/apache/commons/math3/distribution/package-tree.html

GammaDistribution[] initDirichlet(double a, int N) {
    GammaDistribution[] r = new GammaDistribution[N];
    double scale = 1.0;
    for(int k = 0; k != N; ++k)
        r[k] = new GammaDistribution(a, 1.0);
    }
    return r;
}

void sampleDirichlet(double[] r, GammaDistribution[] g, int N) {
    double s = 0.0;
    for (int k = 0; k != N; ++k) {
        double v = g[k].sample();
        r[k] = v;
        s += v;
    }
    s = 1.0 / s;
    for (int k = 0; k != N; ++k) {
        r[k] *= s;
    }
}

void sample(double[] r, GammaDistribution[] g, int N, double d) {
    double mean = 1.0/(double)N;
    outer:
    for( ;; ) {
        sampleDirichlet(r, g, N);
        for (int k = 0; k != N; ++k) {
            if (Math.Abs(r[k] - mean) > d)
                continue outer; // reject and start over
        }
        break; // accept
    }
}

int use() {
    int N = 10;
    double a = 7.0;
    double d = 0.05;
    GammaDistribution[] g = initDirichlet(a, N);

    double[] r = new double[N];

    sample(r, g, N, d);
    sample(r, g, N, d);
    sample(r, g, N, d);
    sample(r, g, N, d);
    sample(r, g, N, d);
    ....
}
Severin Pappadeux
  • 18,636
  • 3
  • 38
  • 64
0

I think the question is a variation/similar to the water pouring problem

https://en.wikipedia.org/wiki/Water_pouring_puzzle

You can choose n cups each of m{i} capacity to pour the desired amount of water.

so choose "n" numbers to sum to "m" .

You can find solutions and tailer it to your use case.

Here is one possible solution:

https://gist.github.com/setrar/77fc1c301266afde9f7f

Avba
  • 14,822
  • 20
  • 92
  • 192