lundi 5 juin 2017

How to create n strings of random lengths the sum of which is equal to a given amount?

I'm trying to create an algorithm to create n strings of random length the sum of which is equal to a given amount.

An example to make it clearer:

total = 20;
n = 7;

strings = ['aaaa', 'a', 'aaaaaaa', 'aa', 'aaa', 'aa', 'a'];

So I have 7 strings of random lengths and the sum of their individual lengths is (unless I made an error counting) 20.

Till now I came up with this recursive function:

gaps = [];
function createGapsArray(total, n) {
    if (n == 1) {
        var gapLength = total;
    } else {
        var gapLength = getRandomInt(1, total / 2);
    }

  var gap = "";
  for (var i = 0; i < gapLength; i++) {
    gap += "a";
  }
  gaps.push(gap);

  if (n > 1 && total > 0) {
    createGapsArray(total - gapLength, --n);
  }
}

Which doesn't really work. Usually it finishes before generating all the n segments I want. With the few tests that I've done, it seems that dividing the total by 4 instead of 2, gets the job done. Like:

var gapLength = getRandomInt(1, total / 4);

But the choice of this constraint is just arbitrary. I'm wondering if there is a better approach to this.

Also, I'm aware that with my approach the algorithm is likely to generate longer segments at first and smaller ones towards the end. I wouldn't mind an even distribution, but it's not a big deal because for what I need it I can simply shuffle the array once it's done.




Aucun commentaire:

Enregistrer un commentaire