CODEWITHSUNDEEP
algorithm
Nick
Nick

Reputation: 8309

Algorithm for Even Distribution

I'm not an algorithms person, so this may be a very simple problem and I just don't know the right terminology to search for. Also, this question has a contrived and unrealistic example, but I think what I'm trying to achieve is clearest this way.

Suppose a website had articles that could be any number of pages long and there was a pool of ads that could have any number of ads in it. The site owner has these requirements:

  1. Each ad should appear exactly 1 time throughout the article's pages
  2. The ads should be evenly distributed among the article's pages
  3. If there are more ads than pages then multiple ads on a single page is OK
  4. Page 1 must always have at least 1 ad

So if an article had 10 pages and there were 5 ads, an ad should be on all of the odd pages as opposed to having the first 5 pages have an ad and the last 5 pages have no ad.

I don't know what to do about the more complex situations. For example, suppose an article had 29 pages and there were 11 ads. You would have an ad on page 1 because of requirement #4, but how could you distribute the rest evenly? If you had an ad on every other page then the 11th ad would appear on page 21, making the final 8 pages have no ads. If you made it so there were 2 pages without an ad in between each page with an ad then you wouldn't use all of the ads (requirement #1). So you would have to do something like alternate between having 1 and 2 pages without ads in between each page with an ad. This would make it so the pages with ads would be pages 1, 3, 6, 8, 11, 13, 16, 18, 21, 23, and 26.

Hopefully what I'm trying to achieve is clear. How can I do this?

Upvotes: 2

Views: 875

Answers (1)

user4843530
user4843530

Reputation:

I have added a fiddle that does this both ways, from page number to ads in that page, and from ads to what pages they go on. You can find it HERE. You can change the number of pages and the number of ads, and the fiddle will give you the results both ways. Mind you, the ads are zero indexed, so the first ad would be "Add 0".

You can loop through the ads and put each one at

for (int AdIndex = 0; AdIndex < NumberOfAds; AdIndex++) {
    PageNum = 1 + math.truncate( ((float) NumOfPages) * (float) AdIndex / (float) NumberOfAds);
}

If you want to do it the other way around, on any given page, add the relevant ads, then on that page, you would do this:

for (adIndex=math.ceiling(((float) PageNum-1.0F)*(float)NumberOfAds / (float) NumberOfPages);
     adIndex<math.ceiling(((float) PageNum)*(float) NumberOfAds/(float) NumberOfPages);
     adIndex++)
{
    AddThisAdToCurrentPage(AdIndex);
}

The basic idea here is that if you want to put N ads in P pages, and you want to distribute them evenly, then the gap in pages is P/N. Unless P is a multiple of N, this will give you a number with decimals. But, here is the secret, you can ignore that fact and calculate the page number with floating point math for any ad as

page number = 1 + (ad number * P/N)

If you make sure that the math is all done with floating points, until you get that page number, then, and only then, round it down to the next lower integer, you will have page numbers that are as evenly distributed as possible. This works regardless of whether P is less than or greater than N.

Turn that equation around and you have:

ad number = (page number - 1) * N/P

If you again do floating point arithmetic all the way, and then only round it UP to the next higher integer when you get the final number, this gives you the first ad that should appear on or after this page. That does not help unless you look at the same formula for the next page and figure out what is the first ad that should appear on or after the next page. If it is the same ad, then it means that ad does not occur on this page. It occurs after this page. If applying the formula to the next page gives you a later ad, then we know we have some ads on this page. Or in a simpler form, we loop adding the ads to this page...

FROM (page number - 1) * N/P   TO  __less than__ (page number) * N/P

And if those two numbers are the same, then the less than causes no ads to be added to the current page. Again, check it out with the provided fiddle. This turns out to be very simple code.

Upvotes: 4

Related Questions