Objective-C how to pull several random items out of NSArray without getting duplicates?

Question

I have an array of random properties I would like to assign to equipment within the game I'm developing.

The code that I use below is returning an NSArray. I'm interested if there's way to get item indices from that array without getting duplicate values. The obvious solution is to create a mutable array with the returned array, do random, remove item that was returned and loop until the number of items is received.

But is there a different way of getting X random items from NSArray without getting duplicates?

//get possible enchantments
NSPredicate *p = [NSPredicate predicateWithFormat:@"type = %i AND grade >= %i", kEnchantmentArmor,armor.grade];

NSArray* possibleEnchantments = [[EquipmentGenerator allEnchantmentDictionary] objectForKey:@"enchantments"];

//get only applicable enchantments
NSArray *validEnchantments = [possibleEnchantments filteredArrayUsingPredicate:p];
NSMutableArray* mutableArray = [NSMutableArray arrayWithArray:validEnchantments];

NSDictionary* enchantment = nil;

if(mutableArray.count>0)
{
    //got enchantments, assign number and intensity based on grade
    for (int i = 0; i<3;i++)
    {
        enchantment = mutableArray[arc4random()%mutableArray.count];
        [mutableArray removeObject:enchantment];

        //create enchantment from dictionary and assign to item.
    }

}

score 7 · Answer 1 · edited May 23 '17 at 12:04

7

You can shuffle the array using one of the following techniques:

What's the Best Way to Shuffle an NSMutableArray?
Non repeating random numbers

Then, take the first X elements from the array.

edited May 23 '17 at 12:04

Community

1
1

answered Jan 04 '14 at 05:19

godel9

7,340
1
33
53

By far the simplest way to do it. OP, I would go with this answer. – pasawaya Jan 04 '14 at 05:23

score 2 · Answer 2 · answered Jan 04 '14 at 06:46

2

Many years ago, I was working on card game and I realized that shuffling the deck was an inefficient way to get random cards. What I would do in your shoes is pick a random element, and then replace it with the element at the end of the array, like so:

@interface NSMutableArray (pickAndShrink)


- (id) pullElementFromIndex:(int) index  // pass in your random value here
{
id pickedItem = [self elementAtIndex:index];
[self replaceObjectAtIndex:index withObject:[self lastObject]];
[self removeLastObject];
return pickedItem;
}

@end

The array will shrink by one every time you pull an element this way.

answered Jan 04 '14 at 06:46

NSResponder

16,861
7
32
46

I'm not sure you are getting really random results here. YOu are taking the last object, putting it in the middle, and then removing another object from the end. In other words, I don't think this code does a swap of selected with last before removing last. – Alex Stone Jan 06 '14 at 17:16
I think this is a good way, but I think it is unnecessary to replace the object that was picked. If you remove it, it is enough, since next time you're going to pick a random index anyway (so that actual order of the remaining items doesn't matter). Also, you could make it "smarter" by doing arc4random%array.count or something so you don't have to pass in a random value - you could automatically get a number in range. – Rahul Iyer Jan 07 '14 at 08:10

Rahul Iyer · Answer 3 · 2014-01-04T05:27:02.420

You could use a random number generator to pick a starting index, and then pick the subsequent indices based on some kind of math function. You would still need to loop depending on how many properties you want.

Eg:

-(NSMutableArray*)getRandomPropertiesFromArray:(NSArray*)myArray
{ 
    int lengthOfMyArray = myArray.count;
    int startingIndex = arc4random()%lengthOfMyArray;
    NSMutableArray *finalArray = [[NSMutableArray alloc]init]autorelease];
    for(int i=0; i<numberOfPropertiesRequired; i++)
    {
       int index = [self computeIndex:i usingStartingIndex:startingIndex        origninalArray:myArray];
       [finalArray addObject:[myArray objectAtIndex:index]];
    }
    return finalArray;
}

-(int)computeIndex:(int)index usingStartingIndex:(int)startingIndex
{
   //You write your custom function here. This is just an example.
   //You will have to write some code to make use you don't pick an Index greater than the length of your array.
   int computedIndex = startingIndex + index*2;
   return startingIndex;
}

EDIT: Even your computeIndex function could use randomness in picking the subsequent indices. Since you have a startingIndex, and another index, you could use that to offset your function so that you never pick a duplicate.

EDIT: If your array is very large, and the subset you need to pick is small, then rather than shuffle the entire array (maybe more expensive), you could use this method to pick the number of items you need. But if your array is small, or if the number of items you need to pick are almost the size of the array, then the godel9's solution is better.

score 1 · Answer 4 · answered Jan 04 '14 at 05:56

1

You can use a mutable array and then remove them as the are selected, use something like random()%array.count to get a random index. If you don't want to modify the array then copy it with [array mutableCopy].

answered Jan 04 '14 at 05:56

Nathan Day

5,981
2
24
40

Objective-C how to pull several random items out of NSArray without getting duplicates?

4 Answers4

Linked