0

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.

user3064209
  • 147
  • 4
  • 14
  • 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 Dec 09 '13 at 22:59
  • so if the array.length() is 1936 you want to expand to 22000, so you're actually adding elements to that array right? – sukunrt Dec 09 '13 at 23:05
  • 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 Dec 09 '13 at 23:08
  • 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 Dec 09 '13 at 23:14
  • 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 [edit]ed into the question rather than just being a comment. – Bernhard Barker Dec 09 '13 at 23:23
  • Heading to work right now, will attempt to improve the question after my shift. – user3064209 Dec 09 '13 at 23:29
  • This is extremely unclear. Here's my interpretation: You want to take a set of data points of size _n_, and create a new set of size _m_, where _m_ can be smaller than or larger than _n_. If _m_ > _n_ you want to keep the two end point values, evenly distribute the existing data points over the new interval, and then somehow "fill in" the empty cells that were inserted between old values to expand the range. If _m_ < _n_ you want to discard some evenly distributed subset of the original values to fit the new, smaller array size, while keeping the first and last values. Is this close? – Jim Garrison Dec 10 '13 at 00:07

2 Answers2

0

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.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • I think the user actually wants to add some numbers, since he's mentioning array length. – sukunrt Dec 09 '13 at 23:05
  • @sukunrt Yeah, I have no idea. I'll just leave this here until I figure out what the question is. – Bernhard Barker Dec 09 '13 at 23:26
  • I think @Dukeling got it pretty close from my flawed question (need to take more math classes!). I do eventually want to have it add some elements to the array, but at the moment scaling (mapping?) is the key. – user3064209 Dec 09 '13 at 23:28
  • @Dukeling - implemented your solution and posted a Java example of the code. Thanks! – user3064209 Dec 12 '13 at 10:37
0

(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.

Community
  • 1
  • 1
Simon
  • 10,679
  • 1
  • 30
  • 44