对一个可变数组(NSMutable 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

任何帮助和建议都将是很好的，我已经在这个问题上忙碌了一整天。

- S1syphus

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

希望这样做可以解决问题！

- Jonas Jongejan

Answer 2

这比看起来难得多... 明显的想法是排序唯一值并循环它们（从最高频率值开始），得到如下结果：

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

我不确定你计算“尽可能远离另一个”的规则是什么，但我认为这个答案是次优的（例如，如果你交换最后一个蓝色和红色的对，它会变得更好）。

感觉像NP完全问题...

- David Gelhar

Answer 3

另一个想法：

首先为每个不同的值创建一个列表，即：

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

然后将它们合并成一个列表，从最大的列表开始，以便在每个第i个位置添加一个新元素。记住最后插入点，以便填充整个列表，而不仅仅是像David Gelhar的答案中一样填充开头。如果到达末尾，请增加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

我不认为这会产生最优解，但对于您的目的来说可能已经足够好了。

- swegi

---

如果你有10个“红色”和2个“绿色”，那么结果将是“红色，绿色，红色，绿色，红色，红色，红色，红色，红色，红色，红色，红色”。 - jasongetsdown

@jasongetsdown：在这种情况下，无论如何都会有很多重复的 Red。 - swegi

没错，但我的意思是两个“绿色”不会尽可能远。 - jasongetsdown

Answer 4

这里有一个想法。首先计算每种类型的数量并将其除以总数。这将告诉您大致上每种类型应该出现的频率（即每第二个索引，每第三个索引等）。

然后遍历数组，为每个元素类型保持计数器。在每个索引处增加所有计数器，然后检查该索引处元素类型的计数器是否高于平均分布。如果是，则将其与前一个元素交换，将该类型的计数器清零，然后继续。如果不是，则继续前进。

这需要多次通过，但最终您将拥有一个均匀分布的列表。我还没有做笔和纸工作，但像这样的东西可能是您最好的选择。

编辑-用笔和纸尝试了一下。如果您开始排序，可能需要与元素数量相同的次数通过。如果您首先随机化，并且每种元素类型的数量相似，则需要的时间会少得多。不过这只是一种猜测...

- jasongetsdown