Generating multiple pages with multiple numbers

Question

This question is mainly related to programming else than just only a math problem, I am developing a system where there will be multiple pages of contents, the contents are coin types and I need to generate a page showing those coin types, the main problem is that the value of the coin types can increase a lot.

Each page can support up to a max of 2880 coin values, but there can be cases where the total coin values would be a number value higher than 300k, meaning an algorithm that generated all pages at once would not be efficient.

A page can end up having multiple content types as long as their sum is less or equal 2880, examples:

Page1:

BONE: 2880

Page2: BONE: 230 ARROW: 532

I would have some sort of logic where if I asked for the contents of page 1 it would tell me bone 2880, as well as if I asked for contents of page 2 would return what page 2 has.

I know the total number of currency values and types, meaning I have a Map<String,Integer> where the key is the name of the currency type, but the value is not formatted into pages etc, it is a number that can be 0 to Integer.MAX_VALUE.

Does anyone have some idea on how I could do this? logical answer helps, it does not have to be in any form of code, I just need help with the logic and math behind it.

To get it straight, you essentially have an ordered list of $(currency,count)$, you know that every count of 2880 represents a new page, and you want to be able to figure out what currencies will go on page $N$? — ConMan, Nov 08 '22 at 06:48

score 1 · Answer 1 · answered Nov 08 '22 at 07:03

Assuming my interpretation (see comment) is correct, then you should be able to do something like the following, which would involve traversing the entire list once.

Given an ordered sequence of counts $a_i$, and where $A$ is the count for a single page:

Calculate the cumulative sums $c_i = \sum_{j = 1}^i a_j$.
Find the first and last page each currency will appear on by checking where the multiples of $A$ land between the cumulative counts.

In algorithmic form, it's something like this:

index = 0
csum = 0
while (index < MAX_INDEX)
  firstpage[index] = ceil((csum + 1) / PAGE_LENGTH)
  csum = csum + count[index]
  lastpage[index] = ceil(csum / PAGE_LENGTH)
end

where ceil() is the ceiling function, and returns the smallest integer greater than or equal to its argument.

What would count be? I can't reproduce it, all I have as data is the target number of page, and the total number of values, like: ARROW: 3824, BONE: 2219 — Pedro Paulo Monte Pagani, Nov 08 '22 at 12:08
$count$ is the number you have - so the first two iterations would give you $csum = 3824$ and $csum = 3824 + 2219 = 6043$. If the list doesn't change often, then it would probably be more efficient to use this to build a second list holding either the values of $firstpage$ and $lastpage$, or the first and last index appearing per page. — ConMan, Nov 08 '22 at 22:33

Generating multiple pages with multiple numbers

1 Answers1