Filtering NSString Objects from an NSMutableArray

Question

My app receives the user's input from a text field and generates all the possible words which can be made from the letters.

If the user types in "BOX", the program generates a mutable array which contains such words as: "BO", "BOB", "BOO", "OX".

I just need to filter out the words which contain duplicate letters that are not present in the user's input. So, I need to filter out "BOB" and "BOO."

I guess another solution would be to avoid generating BOB and BOO in the first place, but I haven't figured that out either.

Thanks!

Martin R · Accepted Answer · 2013-04-30 12:12:01Z

3

To generate all possible combinations from the letters of the given word (where each letter is used only once) you can use the following recursive method:

- (NSArray *)allWordsFrom:(NSString *)word
{
    NSMutableArray *a = [NSMutableArray array];
    [self addAllWordsFrom:word withPrefix:@"" toMutableArray:a];
    return a;
}

- (void)addAllWordsFrom:(NSString *)letters withPrefix:(NSString *)prefix toMutableArray:(NSMutableArray *)a
{
    [letters enumerateSubstringsInRange:NSMakeRange(0, [letters length])
                    options:NSStringEnumerationByComposedCharacterSequences
                 usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) {
                     // Add one letter to the prefix:
                     NSString *word = [prefix stringByAppendingString:substring];
                     [a addObject:word];
                     // Build combinations with remaining letters:
                     NSString *remainingLetters = [letters stringByReplacingCharactersInRange:substringRange withString:@""];
                     if ([remainingLetters length] > 0) {
                         [self addAllWordsFrom:remainingLetters withPrefix:word toMutableArray:a];
                     }
                 }];
}

For the word "BOX" this creates the list

B, BO, BOX, BX, BXO, O, OB, OBX, OX, OXB, X, XB, XBO, XO, XOB

and you don't have to filter the array afterwards.

edited Apr 30, 2013 at 12:12

answered Apr 30, 2013 at 12:06

Martin R

541k98 gold badges1.3k silver badges1.4k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

silverSuns Over a year ago

Thanks a lot for all the help. I would have never figured that out.

Tobias Müller · Accepted Answer · 2013-04-30 12:03:20Z

1

Assuming your array with all possible letters is allCombinations you can use the filteredArrayUsingPredicate function of NSArray to create a filtered array. Therefor you need to define a precidate which can be done easily using a block:

NSPredicate *filterPrecicate = [NSPredicate predicateWithBlock: ^BOOL(id obj, NSDictionary *bind){
    BOOL filterEntry;
    // do actually filtering a set filterEntry to YES/NO
    return filterEntry
}];

After creating the block you can do the filtering:

NSArray *filteredCombinations = [allCombinations filteredArrayUsingPredicate: filterPrecicate];

answered Apr 30, 2013 at 12:03

Tobias Müller

6051 gold badge5 silver badges21 bronze badges

1 Comment

silverSuns Over a year ago

I really need to study blocks some more. I started trying something similar, but I couldn't figure out how to use blocks.

aLevelOfIndirection · Accepted Answer · 2013-04-30 12:08:17Z

Here is the code that will filter your array as requested. You can modify it slightly to use predicate filtering if you like.

NSCountedSet *letterBinsForWord(NSString *word)
{
    NSCountedSet *bins = [NSCountedSet set];
    for (NSUInteger i=0, n=word.length;  i<n;  i++) {
        NSString *letter = [word substringWithRange:NSMakeRange(i, 1)];
        [bins addObject:letter];
    }
    return bins;
}

BOOL letterBinsIncludesBins(NSCountedSet *set0, NSCountedSet *set1)
{
    for (NSString *letter in set1) {
        if ([set0 countForObject:letter] < [set1 countForObject:letter])
            return NO;
    }
    return YES;
}


int main (int argc, const char * argv[])
{
    @autoreleasepool {

        NSString *userText = @"boox";
        NSArray  *words = @[@"box",@"ox",@"boo",@"booo",@"bo",@"bin"];

        NSCountedSet *letterBins = letterBinsForWord(userText);
        NSMutableArray *filteredWords = [NSMutableArray array];

        for (NSString *word in words) {
            NSCountedSet *bins = letterBinsForWord(word);
            if (letterBinsIncludesBins(letterBins, bins))
                [filteredWords addObject:word];
        }

        NSLog(@"Filtered words: %@",filteredWords);
    }
    return 0;
}

For the userText "boox" (with two 'o') I get the following output:

Filtered words: (
    box,
    ox,
    boo,
    bo

This is great. Thanks for taking the time to answer my question.

Collectives™ on Stack Overflow

Filtering NSString Objects from an NSMutableArray

3 Answers 3

1 Comment

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related