Expanding/shrinking a number set to a certain length

0
votes

This is a math question, since it's looking for an algorithm/mathematical function(s) that I can then implement in Java and then later C++. I'm not sure completely what to even search for, but I've tried, so pointing me in better directions on what to look for would be good even, and much appreciated.

So I'm starting off with an arbitrary length set (stored as an array in my program, but that doesn't matter) from [0 - n] and what I'm trying to do is figure out some mathematical formulas (or just pseudocode algorithm) that will expand/shrink that set to a certain length while 0 remains the same, but n changes to a set number, and the numbers between 'expand' or 'shrink' in some manner. I'm guessing it would be similar to resizing an image, but that's not what I'm doing.

Example 1: initial array is array.length() 1936, I'm trying to expand it to 22,000 while maintaining 0 and having the numbers between expanded in some rational way (it doesn't need to be perfect, just reasonable)

Example 2: initial array is array.length() 27,002, so I'd need to shrink it to 22,000 while maintaing 0 and ordering the numbers between during the shrink in some rational way.

I've got no idea what the mathematical term for what I'm looking for is called, or how easy/hard this is to implement in real or even pseudo-code. Help on what to search for is greatly appreciated! Thanks!

edit

here's what I ended up doing for a solution based on @Dukeling's suggestion, obviously there would be a loss of precision in several places, but I'm not overly concerned with that for the purposes I'm writing this, maybe for the beta or later version, but not now (example is in Java):

public class NumberTest
{
    public static void main(String[] args)
    {
        int count;
        double temp;
        int goal = 20000;
        int before = 5029;
        int[] beforeList = new int[before];
        int[] afterList = new int[goal];

        for (count = 0; count < before; count++)
        // this populates the initial array
        {
            beforeList[count] = count;
        }

        for (count = 0; count < before; count++)
        // this creates the resulting set
        {
            temp = (double)beforeList[count]/(double)before * (double)goal;
            afterList[count] = (int)temp;
        }
    }
}

this will create two lists, one that is set to [1-n] where the int 'before' is n, the other (based on this one) where an approximation of 'goal' is the largest #.

I'm not sure if there's a 'cheaper' way to do this as far as processing and/or memory, but this is the best I could come up with so far, and should explain more or less what I'm trying to do.

2
javaarraysalgorithmmathpseudocode
A set doesn't allow duplicates, so if you expand it, you have to use unique numbers, i.e. it appears you can't use integer or you will get duplicates which a Set doesn't allow. – Peter Lawrey
so if the array.length() is 1936 you want to expand to 22000, so you're actually adding elements to that array right? – sukunrt
Can you give an example? I mean when you say expand in some rational way a small example? set of size 5-10 maybe? – sukunrt
So if starting out with set [0-5] and the target is [0-15] something that would result in a set of like [0, 3, 6, 12, 15] Not worried about injecting or predicting the missing values right now. And yes, each number will be unique. – user3064209
Can you be more explicit about your example? Will the output be a set of 5 numbers, or 15? Is the input always a continuous range? And it should be edited into the question rather than just being a comment. – Bernhard Barker

2 Answers

0
votes

If I understand correctly, you want to maintain the ratio of each of the numbers with the maximum.

To do this you need to basically, for each number, divide that number by oldN and multiply it by newN.

So expanding 0,2,4,5 (i.e. in the range 0-5) to 0-20 would become
0/5*20, 2/5*20, 4/5*20, 5/5*20 = 0,8,16,20.

0
votes

(Amended as a result of a later comment in the question by the OP)

It appears that the problem is to map a set of n1 integers in a range [low1 .. hi1] onto another set of size n2 in the range [low2 .. hi2]. That seems to be equivalent to finding the best line across a plane between the points (low1,low2) and (hi1,hi2) where one can only use integers to define the locations of points on the line. A good way to do this is to use the Bresenham algorithm.

If n2 < n1, then the resulting list of integers will have duplicates that will be eliminated when a set is created from the list.