Цель C - Расчет перестановок дубликатов

Question

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

Для алгоритма типа решателя головоломок я извлекаю дублирующиеся буквы как подстроку NSString.Допустим, пользователь вводит «RBEEEIOOUUU». Я вытаскиваю только дубликаты из их строки и хочу видеть каждую возможную комбинацию этих дубликатов, не столько позиционно в строке, сколько просто путем изменения количества повторений .. (для этой проблемыпозиция не имеет значения, я ее алфавитирую позже ..)

Итак, учитывая строку EEEOOUUU, я хочу получить набор всех возможных комбинаций строки, основываясь на существенном изменении дубликатов,

Учитывая этот пример, все возможные строки с 3 или Меньше E, 2 или Меньше O и 3 или Меньше U.

Итак, чуть выше моей головы, я бы хотел вернуть

EEEOOUUU (исходная строка) EEEOUUU EEEOOUU EEEOOU

EEOOUUU EEOUUU EEOOUUU EEOUU EEOUU EOOUUUU ....... и так далее ...

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

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

Для темы разговора вот что-то плохое, что я только что взломал, что, вероятно, все можно выбросить вместо чего-то ... конечно, это предполагает некоторые вызовыя бы позже сказал, что возвращаю только дураки и т. д. Не в восторге от этого как от использования массивов, но это не то, что будет повторяться для множества входных терминов.

//probably the most inefficent way of doign this, sorry for my level of fail.
-(NSMutableArray*) getDuplicatePermutations:(NSMutableArray*)workingArray workingWord:(NSMutableString*)workingWord currentLetter:(NSString*)currentLetter{
    NSArray *dupeArray = [self getDuplicateLetters];  //this returns only the letters with an occurrence >1 so in EEEIIOOOT, it returns "E", I", "O"
    if (workingWord==nil){workingWord = [[NSMutableString alloc] init];
        for (NSString *thisLetter in dupeArray)
        {
            for (NSString* thisLetterStuff in [self possibleDupePermutationsForLetter:thisLetter theWord:self]){  ////this thing returns NSArray of NSStrings like so "EEE","EE", "E"
                workingWord = [workingWord stringByAppendingString:thisLetterStuff];
                if ([thisLetter isEqualToString:[dupeArray lastObject]]) { ///do... something.. at the lowest depth...
                    [workingArray addObject:workingWord];
                    workingWord = @"";
                }
                workingArray = [self getDuplicatePermutations:workingArray workingWord:workingWord currentLetter:thisLetter];  //I can haz recursion?  No idea where to do it,actually.
            }
        }

    }
    return workingArray;    ///ostensibly an array filled with crap the looping mess builds
}

Answer 1

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

Решение было что-то вроде этого.

Для каждой буквы из исходного слова, которая является дубликатом Создайте «Dupe Map», которая по сути представляет собой словарь с ключом буквы и значением числа вхождений "

Поместить часть слова в эту букву (буква * это число появлений - итерация)

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

После каждой итерации внешнего цикла воссоздайте карту дублирования и повторите ее ...

(очевидно, он содержит некоторые другие методы в экземпляре, которые также выполняют утилитарные задачи) Но я, по крайней мере, хотел бы поделиться, даже если это плохо и, возможно, утечка прямо сейчас.

-(NSMutableArray*) DoCrazyCalculationsForDuplicatePermutations
{
    NSMutableArray *resArray = [[NSMutableArray alloc] init];
    NSArray *myDupes = [self getDuplicateLetters];
    for (NSString *thisLetter in myDupes){
        NSMutableDictionary *myDupeMap = [self getDupeMap];
        NSArray *keys = [myDupeMap allKeys];
        NSMutableString *wordSeed = [[NSMutableString alloc] init];
        NSNumber *seedNumberFromDictionary = [myDupeMap objectForKey:thisLetter];
        unsigned seedLettersToMake = [seedNumberFromDictionary intValue];
        [myDupeMap setValue:[NSNumber numberWithInt:1] forKey:thisLetter];  //1 Out the entry for this primary letter because we will handle it as part of the outer loop  -- also prevents 1 infinite loop below
        unsigned w = 0;
        for (w=1; w <= seedLettersToMake; w++) {
            myDupeMap = [self getDupeMap];  //reset the dupe map...
            [wordSeed appendString:[self getLettersByLetterAndCount:thisLetter count:1]];  //I will be appended inside the loop, per word;
            unsigned dupeTotals = [myDupeMap myTotals];
            while (dupeTotals >= ([myDupeMap count])) {
                NSMutableString *thisWord = [[NSMutableString alloc] init];
                [thisWord appendString:wordSeed];
                for (NSString *thisKey in keys){
                    if(![thisKey isEqualToString:thisLetter]){
                        NSNumber *numberFromDictionary = [myDupeMap objectForKey:thisKey];
                        unsigned lettersToMake = [numberFromDictionary intValue];//how many for this letter? 
                        [thisWord appendString:[self getLettersByLetterAndCount:thisKey count:lettersToMake]];
                        if (lettersToMake > 1){
                            unsigned o = lettersToMake - 1;
                            [myDupeMap setValue:[NSNumber numberWithInt:o] forKey:thisKey];
                            dupeTotals = [myDupeMap myTotals];
                        }
                    }
                }
                if (([thisWord length]-(w-1)) == ([myDupeMap count])) {dupeTotals=.5;} //break out
                NSLog(@"CrazyDuplicateProcessing: %@",[thisWord alphabetized]);
                [resArray addObject:thisWord];
            }
        }
    }
    return resArray;
}

Answer 2

Если я понимаю, что вы просите, это можно сделать с помощью вложенных циклов. В псевдокоде:

for e-count in 1 to 3:
    for o-count in 1 to 2
        for u-count in 1 to 3:
            create string with e-count e's, o-count o's and u-count u's