Сортировка / перемешивание NSMutuable Array

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

Надеюсь, что это делает!

Answer 2

Это сложнее, чем кажется ... Очевидная идея сортировки уникальных значений и их циклического перебора (начиная с самых высоких частот) дает что-то вроде:

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

Я не уверенкаково ваше правило для вычисления «как можно дальше от другого», но я думаю, что ответ является неоптимальным (например, если вы поменяете местами последнюю пару «синий», «красный», он улучшится)....

Answer 3

Другая идея:

Сначала составьте список для каждого отдельного значения, то есть:

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

Затем объедините их в один список, начиная с самого большого списка, так, чтобы появился новый элементдобавляется на каждой i-й позиции.Помните последнюю точку вставки, чтобы вы заполнили весь список, а не только начало, как в ответе Дэвида Гелхара.Увеличьте i, если вы достигнете конца:

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

Я не думаю, что это даст оптимальное решение, но оно может быть достаточно для ваших целей.

Answer 4

Вот идея. Сначала подсчитайте количество каждого типа и разделите на общее. Это примерно скажет вам, как часто должен появляться каждый (то есть каждый второй индекс, каждый третий и т. Д.).

Затем выполните итерацию по массиву, сохраняя счетчики для каждого типа элемента. При каждом увеличении индекса все счетчики, а затем проверьте, превышает ли счетчик для типа элемента с этим индексом среднее распределение. Если это затем заменить его на предыдущий элемент, обнулить счетчик для этого типа и двигаться дальше. Если не просто двигаться дальше.

Это займет несколько проходов, но в итоге вы получите равномерно распределенный список. Я не занимался ручкой и бумагой, но это будет лучшим выбором.

Редактировать - Пробовал с ручкой и бумагой. Если вы начнете сортировать, это, вероятно, займет столько проходов, сколько у вас будет элементов. Если вы рандомизируете сначала, и если число элементов каждого типа будет одинаковым, это займет гораздо меньше времени. Это все только рука машет рукой ...