Sort / Move NSMutuable Array

Question

I'm just starting to enter Objective-C, I'm trying to sort an array so that it is as small 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's not as low a mismatch as we would like because of a random number.

Ideally, each instance should be as far from the other as possible:

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

Any help and suggestions would be great, I'm going to do this almost all day.

Answer 1

Ok, I sat and tried to create an algorithm that shuffles the array. I think this is a decent job, but it can probably be improved. This is done quickly.

I calculate the frequency of each color and use this to move the array of results. For each object, as a result, I use a frequency to determine which color to add now. There are several if statements for this.

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; 

Result:

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

I hope so!

Answer 2

This is more complicated than it seems ... The obvious idea of ​​sorting unique values ​​and looping through them (starting with the highest 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 is “as far away as possible”, but I think the answer is suboptimal (for example, if you change the last blue, red pair, it improves).

It smells NP-full ...

Answer 3

Here is an idea. First, calculate the amount of each type and divide it by the total. This will tell you approximately how often each should appear (i.e., every second index, every third, etc.).

Then iterate over the array, saving counters for each type of element. For each index, increment all the counters, then check if the counter for the type of item in this index is larger than the average. If it then replaces it with the previous element, zero counter for this type and go to it. If not just move on.

This will take several passes, but in the end you will have a uniformly distributed list. I did not do a pen and paper work, but something like this would be your best choice.

Change I tried it with a pen and paper. If you start sorting, it will probably take as many passes as you have items. If you randomize first, and if the number of elements of each type is the same, it will take much less time. It’s all just waving, though ...

Answer 4

Another idea:

First create a list for each individual value, i.e.:

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

Then combine them into one list, starting from the largest list, so that a new element is added to each i-th position. Remember the last insertion point so that you fill out the entire list, not just the beginning, 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 do not think this will create the optimal solution, but it can be good enough for your purposes.