对NSMutuable阵列进行排序/混洗

Question

我刚刚开始进入Objective-C,我正在尝试对数组进行排序,以便尽可能地降低差异.

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;
}

哪个输出像

     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

这会使阵列混乱,但由于随机数,它并没有我想要的那么低的差异.

理想情况下,每个实例应尽可能远离另一个实例,例如:

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

任何帮助和建议都会很棒,我几乎整天都在这里.

Answer 1

好吧,我一直坐着试图制作一个洗牌的算法.我认为它做得不错,但可能会有很大改进.它做得很快.

我计算每种颜色的频率,并使用它来遍历结果数组.对于结果中的每个对象,我使用频率来确定现在要添加的颜色.有几个if语句可以做到这一点.

这是代码:

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;

结果是:

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

希望能做到!