Objective C - 重复项的排列计算

Question

我似乎真的想不出一种方法来解决这个问题，出于某种原因我无法思考它。我试图解决的问题是：

对于解谜类型算法，我将重复的字母作为 NSString 的子字符串。假设用户输入“RBEEEIOOUUU” 我只是从字符串中提取重复项，并希望查看这些重复项的每种可能的组合，而不是在字符串中的位置太多，而只是通过改变重复计数来查看。 （对于这个问题的位置并不重要，我稍后按字母顺序排列..）

所以，给定字符串 EEEOOUUU， 我想基于本质上改变重复项来导出一组所有可能的字符串组合，

在这个例子中，所有可能的字符串都带有 3 个或更少的 E、2 个或更少的 O 以及 3 个或更少的 U。

所以，就在我的脑海中，我想返回

EEEOOUUU （源字符串） 伊欧欧欧 EEEOU 啊啊啊啊

啊啊 埃欧乌乌 埃欧乌乌 埃欧乌 埃欧大学 埃奥乌乌 ......等等......

由于某种原因，递归在这方面占据了我的地位，我什至无法想象解决方案。 我有用于固定长度字母组排列的算法，但这在这里没有帮助，或者至少我可怜的睡眠不足的大脑无法应用它们。

任何慷慨的人可能愿意提供的帮助或建议，我将感激不尽。

对于谈话的主题，这里有一些不好的东西，我刚刚乱七八糟的，可能可以全部扔掉以代替某些东西......当然，这假设了一些调用，我稍后会充实这些调用，以仅返回受骗者等。对此作为数组的使用并不感到兴奋，但它不会对一堆条目术语重复。

//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