객관적인 C - 중복의 순열 계산

Question

나는이 문제를 해결할 방법을 정말로 생각하지 못하고, 어떤 이유로 든 주위에 두뇌를 갖출 수 없습니다. 내가 해결하려고하는 문제는 다음과 같습니다.

퍼즐 해법 유형 알고리즘의 경우 NSString의 하위 문자열로 중복 문자를 가져옵니다. 사용자가 "RBEEEIOOUUU"를 입력했다고 가정 해 봅시다. 문자열에서 중복 된 문자열을 가져 와서 중복 문자열의 가능한 모든 조합을 볼 수 있습니다. 반복 횟수를 변경하면됩니다. (for 이 문제의 위치는 내가 나중에 알파벳순, 중요하지 않습니다 ..) 그래서

, 문자열 EEEOOUUU 주어진 을 나는 본질적으로 변화하는 중복 기반으로, 문자열의 가능한 모든 조합의 집합을 도출 할

이 예에서는 3 이하의 E, 2 이하의 O 및 3 이하의 U를 갖는 모든 가능한 문자열을 제공합니다.

그래서, 그냥 내 머리 위로 떨어져, 나는

EEEOOUUU (소스 문자열) EEEOUUU EEEOOUU을 반환 할 것 EEEOOU

EEOOUUU EEOUUU EEOOUUU EEOUU EEOU EOOUUU ....... 등등 ...

재귀는 어떤 이유로이 하나를 소유하고 있습니다. 솔루션을 시각화합니다. 고정 길이의 글자를 순열하기위한 알고리즘을 가지고 있지만 여기서는 도움이되지 않거나 최소한 가난한 수면을 취하지 않은 두뇌는 적용 할 수 없습니다. 여기에 대화의 주제를

관대 제공하게 기꺼이 할 수 있습니다 기분이 어떤 도움이나 제안 사람이, 내가 당신에게 빚을 수 있습니다 ..

은 아마 모두 폐기 할 수 있다는 것을 나는 그냥 해킹 나쁜 일이다 어떤 것 대신에 .... 물론 이것은 나중에 내가 속은 사람 등을 돌려주기 위해 나중에 부름을 줄 것이라고 가정한다. 이것을 배열의 사용으로 오싹하게 여기지는 않겠지 만, 엔트리 용어의 무리.

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

글쎄, 난 어쩌면 누군가가 내 문을 노크하고 ..이 내 운전 면허증과 컴퓨터를 멀리 걸릴 것 같은 느낌 그러나 여기 .. ​​

간다 .. 작동하는 방법을 발견

해결책은 다음과 같습니다. 중복 은 "계산 본질적으로 문자의 키와 발생의 값을 사전 인"속는 맵 "빌드입니다 소스 단어에서 각 문자에 대한

씨 단어 부분 이 문자 (문자 수 * 발생 횟수 - 반복 횟수)

사전에있는 모든 다른 문자에 대해 해당 문자의 가능한 반복에서 하나의 wordpart를 작성하여 반복 횟수를 줄였습니다.외부 루프의 각 반복 후

의 속는지도를 다시 그리고 다시 할 ...

는 (분명히이뿐만 아니라 실용적인 작업을하고있는 인스턴스에 대한 몇 가지 다른 방법을 포함) 를하지만 적어도 지금은 나쁘고 아마도 누출 되더라도 공유하고 싶었습니다.

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