Objective C - Permutations Calculation of Duplicates...

Question

I can't seem to really think of a way to solve this one, can't get my brain around it for some reason. The problem I'm trying to solve is this:

For a puzzle-solver type algorithm, I'm pulling the duplicate letters as a substring of an NSString. Let's say the user enters "RBEEEIOOUUU" I'm pulling just the duplicates from their string, and want to see every possible combination of those duplicates, not so much positionally in the string but just by varying the repetition count.. (for this problem position doesn't matter, I alphabetize it later..)

So, given the string EEEOOUUU, I want to derive a set of all possible combinations of the string, based on essentially varying the duplicates,

Given this example, all possible strings with 3 or Less E's, 2 or Less O's and 3 or Less U's.

So, just off the top of my head, I'd want to return

EEEOOUUU (the source string) EEEOUUU EEEOOUU EEEOOU

EEOOUUU EEOUUU EEOOUUU EEOUU EEOU EOOUUU ....... and so on down...

Recursion owns me on this one for some reason, I can't even visualize the solution. I have algorithms for permutations of sets of letters of fixed length but that doesn't help here or at least my poor sleep deprived brain can't apply them.

Any help or suggestions someone feeling generous may be willing to provide, I'll be indebted to you..

For the topic of conversation here's something bad I just hacked up that probably can be all thrown away in lieu of something.... of course this assumes some calls that'd I'd flesh in later for returning only the dupes, etc. Not thrilled with this as a use of arrays but it's not something that's going to be repeated for a bunch of entry terms.

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

If I understand what you are asking for, this can be done with nested loops. In pseudo-code:

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

Answer 2

Well, I found a way that works.. I feel like maybe someone will knock on my door and take away my driver's license and computer for this.. But here goes..

The solution was something like this.

For each letter from the source word that is a duplicate Build a "Dupe Map" which is essentially a dictionary with a key of the letter and a value of the occurrence count"

Seed the word part with this letter (Letter * it's occurrence count - iteration)

for every other letter in the dictionary, iterate through, dropped the occurrence count by one building wordparts from the possible iterations of those letters.

After every iteration of the outer loop, recreate the dupe map and do it again...

(obviously this contains some other methods on the instance that are doing utilitarian tasks as well) But I at least wanted to share, even if it is bad and possibly leaky right now.

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