Sorting/Shuffling an NSMutuable Array

Question

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

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!

Answer 2

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