Есть ли способ сортировки NSString?

Question

Кто-нибудь знает, существует ли метод для сортировки NSString символов ASCII? В идеале мне нужен метод, который проверяет, является ли одна строка перестановкой другой, поэтому моя идея состоит в том, чтобы отсортировать обе строки каноническим образом и затем сравнить их. Любые идеи будут с благодарностью. Спасибо.

РЕДАКТИРОВАТЬ: Вот то, что я за более точным. Я хочу метод, который принимает два NSStrings в качестве ввода и возвращает BOOL:

- (BOOL)isPermutation:(NSString *)string1 
             ofString:(NSString *)string2; 

Возвращаемое значение должно быть YES, если одну строку можно переставить в другую строку, и NO в противном случае.

Строки NSS - это произвольные строки с символами ASCII , а не предложения, числа или слова. Просто произвольные строки с символами ASCII.

Answer 1

Вам действительно нужно отсортировать, чтобы проверить это? Рассмотрим алгоритм.

create 2 counter arrays, ac and bc, both of size 128
initialize them with 0
for each char c in string a make ac[c]++
for each char c in string b make bc[c]++
if all 128 counters in ac and bc are same, then they r permutation of one another

Это может работать даже быстрее, чем сортировка.

РЕДАКТИРОВАТЬ: Это возможная реализация. Поскольку я не скомпилировал код, возможны незначительные ошибки.

- (BOOL)isPermutation:(NSString *)string1 ofString:(NSString *)string2 {
    if ([string1 length] != [string2 length]) {
        return FALSE;    
    }

    NSInteger counter1[128];
    NSInteger counter2[128];
    NSInteger i;
    NSInteger len = [string1 length];

    for (i = 0; i < 128; i++) {
        counter1[i] = counter2[i] = 0;
    }

    for (i = 0; i < len; i++) {
        unichar ch1 = [string1 characterAtIndex:i];
        unichar ch2 = [string2 characterAtIndex:i];
        counter1[ch1]++;
        counter2[ch2]++;
    }

    for (i = 0; i < 128; i++) {
        if (counter1[i] != counter2[i]) {
            return FALSE;
        }
    }

    return TRUE;
}

Answer 2

Вы имеете в виду сортировку букв внутри строки?На NSString нет метода, но его было бы довольно легко создать. Вот быстрый и грязный пример (вам может потребоваться адаптировать его к вашим целям):

#import <Foundation/Foundation.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

static int compare_char(const char *a, const char *b)
{
    if (*a > *b) {
        return 1;
    } else if (*a < *b) {
        return -1;
    } else {
        return 0;
    }
}

@interface NSString (Sorting)
- (NSString *)stringBySortingCharacters;
@end

@implementation NSString (Sorting)
- (NSString *)stringBySortingCharacters
{
    const char *s = [self UTF8String];
    char *s2 = (char *) calloc([self length]+1, 1);
    if (!s2) return nil;
    strncpy(s2, s, [self length]);
    qsort(s2, [self length], 1, compare_char);
    NSString *ret = [NSString stringWithUTF8String:s2];
    free(s2);
    return ret;
}
@end

int main(int argc, char **argv)
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

    NSString *s1 = @"string";
    NSString *s2 = @"the quick brown fox jumps over the lazy dog";
    printf("Sorted: %s\n", [[s1 stringBySortingCharacters] UTF8String]);
    printf("Sorted: %s\n", [[s2 stringBySortingCharacters] UTF8String]);

    [pool release];
    return 0;
}

Answer 3

Если ваши символы всегда ASCII, вы можете извлечь байты, а затем использовать одну из процедур сортировки POSIX:

char myCString[[myNSString length] + 1];
memcpy(myCString, [myNSString UTF8String], [myNSString length]);

qsort(myCString, [myNSString length], 1, compareChars); 

Где compareChars() - функция, в которую вы написалипроведите сравнение между символами - возможно, в этом случае просто <.