Sorting/Shuffling an NSMutuable Array

Question

Hi,

Im just starting getting into Objective-C, i'm trying to sort an array so it is as low discrepancy as possible.

int main()
{
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    NSMutableArray *myColors;

    myColors = [NSMutableArray arrayWithObjects: @"Red", @"Red",@"Red", @"Red", @"Red", @"Green", @"Green", @"Green", @"Blue", @"Blue", @"Blue", @"Yellow", nil];


    srandom(time(NULL));
    NSUInteger count = [myColors count];
    for (NSUInteger i = 0; i < count; ++i) {
        int nElements = count - i;
        int n = (random() % nElements) + i;
        [myColors exchangeObjectAtIndex:i withObjectAtIndex:n];
         NSLog (@"Element %i = %@", i, [myColors objectAtIndex: i]);
    }

[pool drain]; return 0;
}

Which outputs something like

     Element 0 = Blue
     Element 1 = Green
     Element 2 = Yellow
     Element 3 = Blue
     Element 4 = Green
     Element 5 = Red
     Element 6 = Red
     Element 7 = Red
     Element 8 = Blue
     Element 9 = Green
     Element 10 = Red 
     Element 11 = Red

Which shuffles the array, but it isn't as low discrepancy as I would like due to random number.

Ideally each instance should be as far away from another one of it's kind as possible like:

Red, Green, Red, Blue, Red, Green, Yellow, Red, Blue, Red, Green, Blue

Any help and suggestions would be greats, I've been going at this pretty much all day.

Answer 1

This is harder than it looks... The obvious idea of sorting unique values and cycling through them (starting with the highest-frequency values) gives something like:

Red, Green, Blue, Yellow, Red, Green, Blue, Red, Green, Blue, Red, Red

I'm not sure what your rule for calculating the "as far away from another" is, but I think that answer is suboptimal (for example, if you swap the last Blue,Red pair, it improves).

Smells NP-complete...

Answer 2

Here's an idea. First calculate the number of each type and divide into the total. This would tell you approximately how often each should appear (i.e. every second index, every third, etc).

Then iterate through the array, keeping counters for each element type. At each index increment all the counters, then check if the counter for the element type at that index is higher than the average distribution. If it is then swap it with the previous element, zero the counter for that type, and move on. If not just move on.

It would take multiple passes but you would eventually have an evenly distributed list. I haven't done the pen and paper work, but it something like this is going to be your best bet.

Edit - Tried it with pen and paper. If you start sorted it would probably take as many passes as you have elements. If you randomize first, and if the number of each type of element is similar, it would take much less time. This is all just arm waving though...

Answer 3

Another idea:

First make a list for each distinct value, i.e.:

Red, Red, Red, Red, Red
Green, Green, Green
Blue, Blue, Blue
Yellow

Then merge them into one list, starting with the biggest list, such that a new element is added at every i-th position. Remember the last insertion point so that you fill the entire list and not only the begining as in David Gelhar's answer. Increment i if you reach the end:

Red, Red, Red, Red, Red // i = 1
Red, Green, Red, Green, Red, Green, Red, Red // i = 2
Red, Green, Red, Green, Red, Green, Red, Blue, Red // wrap-around, increment i
Red, Green, Blue, Red, Green, Blue, Red, Green, Red, Blue, Red // i = 3 
Red, Green, Blue, Red, Green, Blue, Red, Green, Yellow, Red, Blue, Red // i = 3

I don't think that this will produce the optimal solution, but it might be good enough for your purposes.

Answer 4

Okay, i've been sitting and trying to make an algorithme that shuffles an array. I think it does a decent job, but can probably be improved a lot. Its done quickly.

I calculate the frequency of each color, and use that for traversing the result array. For each object in the result i use the frequency to determine what color to add now. There are several if statements to do that.

This is the code:

NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
NSMutableArray *myColors;
myColors = [NSMutableArray arrayWithObjects: @"Red", @"Red",@"Red", @"Red", @"Red", @"Green", @"Green", @"Green", @"Blue", @"Blue", @"Blue", @"Yellow", nil];

NSMutableArray * input = myColors;
NSMutableArray * result = [NSMutableArray arrayWithCapacity:[input count]];

//Start by sorting the array
[input sortUsingDescriptors:[NSArray arrayWithObject:[[[NSSortDescriptor alloc] initWithKey:@"self" ascending:NO] autorelease]]];

//Calculate the frequency of each color
NSString * lastValue;   
NSMutableArray * calcDict = [NSMutableArray array];
int i=0;
for(NSString * value in myColors){
    if(lastValue != value || i == [input count]-1){
        if(index >= 0){
            double freq = [input count]/[[[calcDict lastObject] valueForKey:@"count"] doubleValue];
            [[calcDict lastObject] setValue:[NSNumber numberWithDouble:freq] forKey:@"freq"];
            [[calcDict lastObject] setValue:[NSNumber numberWithDouble:-freq / 2.0] forKey:@"lastPosition"];
        }

        if(i != [input count]-1){
            [calcDict addObject:[NSMutableDictionary dictionaryWithObjectsAndKeys:
                                 [NSNumber numberWithInt:0],@"count",
                                 value,@"value",nil]];
            lastValue = value;
        }
    }
    [[calcDict lastObject] setValue:[NSNumber numberWithInt:[[[calcDict lastObject] valueForKey:@"count"] intValue]+1] forKey:@"count"];        
    i++;
}

//Sort the calcDict so the one with lowest frequency is first
[calcDict sortUsingDescriptors:[NSArray arrayWithObject:[[[NSSortDescriptor alloc] initWithKey:@"count" ascending:NO] autorelease]]];

//Calculate the result
for(int i=0;i<[input count];i++){
    //Find the color that matches best
    NSDictionary * bestItem = nil;
    for(NSDictionary * dict in calcDict){
        //The distance to where it prefers to be (based on frequency)
        double bestOptimalPositionDistance = ([[bestItem valueForKey:@"freq"]doubleValue]- (i - [[bestItem valueForKey:@"lastPosition"] intValue]) );           

        if(bestItem == nil) //Always use the first item as base since its sorted
            bestItem = dict;
        else {
            if([[bestItem valueForKey:@"lastPosition"] intValue] >= 0){  //If the best item is already added to the result
                double optimalPositionDistance = ([[dict valueForKey:@"freq"]doubleValue] - (i - [[dict valueForKey:@"lastPosition"] intValue]));                   
                if([[dict valueForKey:@"lastPosition"] intValue] < 0){ //if the dict we are looking at is NOT added to the result earlier on
                    if (bestOptimalPositionDistance > 1 || optimalPositionDistance  < 1) { //find out if the dict is more important than the bestItem
                        bestItem = dict;
                    }
                } else if(optimalPositionDistance < bestOptimalPositionDistance){ 
                    bestItem = dict;
                }

            }
        }

    }

    //Add the best item, and update its properties
    [bestItem setValue:[NSNumber numberWithInt:[[bestItem valueForKey:@"count"] intValue]-1] forKey:@"count"];
    [bestItem setValue:[NSNumber numberWithInt:i] forKey:@"lastPosition"];

    [result addObject:[bestItem valueForKey:@"value"]];
    //If there are added enough of the type of color, delete it!
    if([[bestItem valueForKey:@"count"] intValue] <= 0){
        [calcDict removeObject:bestItem];
    }
}

NSLog(@"result: %@",result);

[pool drain]; return 0;

The result of this is:

Red, Green, Red, Blue, Red, Green, Yellow, Red, Green, Blue, Red, Blue

Hope that does it!