macOS Produce every possible letter combination of a specific word

[MythicFrost]

Hi,

I'm trying to make my program produce every possible letter combination, for example, with the word "one".

This is what I've got so far, I don't understand how to do it properly:

        NSString *word = @"one";
	NSString *newWord = @"";
	for (int i=0;i<[word length];i++){
		NSString *sub = [self getSubstring:word:i:i+1];
		newWord = [self concantenateStrings:newWord:sub];
		newWord = [self concantenateStrings:newWord:@" "];
	}
	NSArray *letters = [newWord componentsSeparatedByString:@" "];
	for (int i=0;i<[letters count];i++) {
	        NSString *temp = [letters objectAtIndex:i];
	        for (int k=0;k<[letters count];k++) {
			if (i != k) {
				temp = [self concantenateStrings:temp:[letters objectAtIndex:k]];
			}
			
		}
		NSLog(@"temp: %@", temp);
	}
	
}

-(NSString*)getSubstring:(NSString *)substring:(int)start:(int)end {
	
	NSString *returnString = [[substring substringToIndex:end] substringFromIndex:start];
	return returnString;
	
}
-(NSString*)concantenateStrings:(NSString*)string1:(NSString*)string2 {
	return [string1 stringByAppendingString:string2];
}

The following code produces one, noe, eon, one, which isn't right... any thoughts on what to do?

Kind Regards

 

[robbieduncan]

Permutation is often handled with a recursive method. The base case for this is when there is a single letter: then there is (obviously) a single permutation. If there is more than one letter strip the first letter off and call the function/method on the remainder. Then insert the letter you stripped into ever position in every returned string.

So something like:

- (NSArray *) permute:(NSString *) string
{
  if ([string length]<2) // Note that this also handles the case when we are asked to permute @""
  {
    return [NSArray arrayWithObjects:string,nil];
  }
  else
  {
    NSString *toPermute = [string substringFromIndex:1];
    NSString *head = [string subStringToIndex:1];
    NSArray *permuted = [self permute:toPermute];
    int i;
    NSMutableArray *combined = [NSMutableArray array];
    for (i=0;i<[permuted count];i++)
    {
      [array addObjectsFromArray:[self insertString:head atEachPositionIn:[permuted objectAtIndex:i]]];
    }
    return combined;
  }
}

- (NSArray *) insertString:(NSString *) toInsert atEachPositionIn:(NSString *) stringToInsertInto
{
// This is left as an exercise for you: it should return an array of strings where toInsert is inserted into each position in stringToInsertInto.  So a call with @"a" and @"bc" should return [@"abc",@"bac",@"bca"]
}

Note I've just typed that straight into here: it's probably got typos and errors!

 

[MythicFrost]

Thanks for your reply,

[array addObjectsFromArray:[self insertString:head atEachPositionIn:[permuted objectAtIndex:i]]];

This line shows an error saying: "array" is unknown, I changed array to combined, is that correct?

Regarding my exercise )), this is what I have so far:

- (NSArray *) insertString:(NSString *) toInsert atEachPositionIn:(NSString *) stringToInsertInto
{
	// This is left as an exercise for you: it should return an array of strings where toInsert is inserted into each position in stringToInsertInto.  So a call with @"a" and @"bc" should return [@"abc",@"bac",@"bca"]
	NSMutableArray *temp = [NSMutableArray array];
	for (int i = 0; i < [stringToInsertInto length]; i++) {
		NSMutableString *test = (NSMutableString*)stringToInsertInto;
		[test insertString:toInsert atIndex:i];
		NSLog(@"test: %@", test);
	}
	return temp;
}

I'm trying to simply insert toInsert at each index, however I get an error when I run the code, it says: "Attempt to mutate immutable object with insertString:atIndex:".

Any thoughts?

Kind Regards

 

[robbieduncan]

This line shows an error saying: "array" is unknown, I changed array to combined, is that correct?

Yes. I said that there were probably errors but that wasn't intentional

NSMutableString *test = (NSMutableString*)stringToInsertInto;

This is wrong. Not just on Objective-C but in all Object-Oriented languages. You can cast an instance up the tree (that is to a super class) but you can never cast down the tree. stringToInsertInto is a NSString. As NSMutableString inherits from NSString you cannot cast in this direction. You need to create a mutable copy:

NSMutableString *test = [NSMutableString stringWithString:stringToInsertInto];

This will also solve the other logical error with your code: as you never copied the string you would insert the string to be inserted between every letter in the same object. So in the example I gave you would get

[@"abaca"]

Which is not what you want. You need a new copy of the original string each time round the loop.

 

[qtx43]

Just as a general comment, when you're doing something like this, it's sometimes better to break the problem into smaller pieces. You're trying to figure out the algorithm and learn objective-c at the same time, and you don't know why you're getting the incorrect result. It's too much random poking around. Robbieduncan has implicitly suggested one algorithm that works by giving you an actual implementation (albeit not complete), so you're over the hump this time. But in the future, it may help to sit and think more deeply about the algorithm and/or data structure first. Or look it up, and then think about why it works, how it works, each step of the process of it working. When you have a working mental model of how the algorithm works, then you can start coding productively. In the long run, it's actually faster.

 

[gnasher729]

Hi,

I'm trying to make my program produce every possible letter combination, for example, with the word "one".

This is what I've got so far, I don't understand how to do it properly:

        NSString *word = @"one";
	NSString *newWord = @"";
	for (int i=0;i<[word length];i++){
		NSString *sub = [self getSubstring:word:i:i+1];
		newWord = [self concantenateStrings:newWord:sub];
		newWord = [self concantenateStrings:newWord:@" "];
	}
	NSArray *letters = [newWord componentsSeparatedByString:@" "];
	for (int i=0;i<[letters count];i++) {
	        NSString *temp = [letters objectAtIndex:i];
	        for (int k=0;k<[letters count];k++) {
			if (i != k) {
				temp = [self concantenateStrings:temp:[letters objectAtIndex:k]];
			}
			
		}
		NSLog(@"temp: %@", temp);
	}
	
}

-(NSString*)getSubstring:(NSString *)substring:(int)start:(int)end {
	
	NSString *returnString = [[substring substringToIndex:end] substringFromIndex:start];
	return returnString;
	
}
-(NSString*)concantenateStrings:(NSString*)string1:(NSString*)string2 {
	return [string1 stringByAppendingString:string2];
}

The following code produces one, noe, eon, one, which isn't right... any thoughts on what to do?

Kind Regards

I'd first switch to using (at least mostly) ordinary C instead of Objective-C. You just produce endless lines of inefficient code without any advantage from it. And you are fighting with getting the Objective-C right when getting the logic right is hard enough.

Second, how many different ways are there to arrange the ten letters abcdefghij ? Somehow I think a double nested loop won't be able to produce all of them. Recursion is one way to handle this.

Third, what if your word is "three", you know with two e's? Well, any word will start with t, h, r or e, but not again with e. There is a very, very simple criterion which letters can come first.

 

[MythicFrost]

This is wrong. Not just on Objective-C but in all Object-Oriented languages. You can cast an instance up the tree (that is to a super class) but you can never cast down the tree. stringToInsertInto is a NSString. As NSMutableString inherits from NSString you cannot cast in this direction. You need to create a mutable copy:

Ah, got it. Thanks.

Just as a general comment, when you're doing something like this, it's sometimes better to break the problem into smaller pieces. You're trying to figure out the algorithm and learn objective-c at the same time, and you don't know why you're getting the incorrect result. It's too much random poking around. Robbieduncan has implicitly suggested one algorithm that works by giving you an actual implementation (albeit not complete), so you're over the hump this time. But in the future, it may help to sit and think more deeply about the algorithm and/or data structure first. Or look it up, and then think about why it works, how it works, each step of the process of it working. When you have a working mental model of how the algorithm works, then you can start coding productively. In the long run, it's actually faster.

I know, I was trying to figure things out in my head, but I just couldn't understand it.

I'd first switch to using (at least mostly) ordinary C instead of Objective-C. You just produce endless lines of inefficient code without any advantage from it. And you are fighting with getting the Objective-C right when getting the logic right is hard enough.

Second, how many different ways are there to arrange the ten letters abcdefghij ? Somehow I think a double nested loop won't be able to produce all of them. Recursion is one way to handle this.

Third, what if your word is "three", you know with two e's? Well, any word will start with t, h, r or e, but not again with e. There is a very, very simple criterion which letters can come first.

C would be harder for me, I don't come from a C background. I initially learned coding from Visual Basic... , I tried C++ and couldn't understand it at the time.

I'm trying, as you said, to figure out how to make letters that have been first, from going again if multiples exist.

Thanks all, it is working.

 

[robbieduncan]

C would be harder for me, I don't come from a C background. I initially learned coding from Visual Basic... , I tried C++ and couldn't understand it at the time.

I'm trying, as you said, to figure out how to make letters that have been first, from going again if multiples exist.

Thanks all, it is working.

C is not C++. Everyone should understand C before writing any Objective C. Otherwise how do you understand what pointers are?

 

[pacmania1982]

Just out of curiosity, as I know nothing of programming, why is it all NS stuff? as in NSString or NSArray?

What is NS?

pac

 

[robbieduncan]

Just out of curiosity, as I know nothing of programming, why is it all NS stuff? as in NSString or NSArray?

What is NS?

pac

Cocoa comes from NeXTStep, the OS/company that Steve Jobs founded when he was kicked out of Apple. Apple later bought the company, used NeXTStep as the basis for OSX and got Steve back as CEO. NS is sometimes assumed to be for NeXTStep although there is some disagreement over that.

The basic reason for having any prefix like NS is that Objective-C does not support namespaces so having a unique prefix prevents name clashes.

 

[MythicFrost]

C is not C++. Everyone should understand C before writing any Objective C. Otherwise how do you understand what pointers are?

Trial and error, and then being told what a pointer is. I started off with VB because I couldn't understand C++ or any complex language, eventually I got into a bit of VC++, and have gradually learned, particularly after I started needing to include a lot of C++ APIs in my programs

I also recently learned how to make an iPhone app, and an iPad app. So, transition to Mac programming hasn't been too much of a learning curve.

Thank you again though, appreciate the help a lot. I know I'm way out of my league here, because even looking at that code you provided (although I've got it working) I still can't understand it fully, perhaps I should just stare a little longer

 

[robbieduncan]

I still can't understand it fully, perhaps I should just stare a little longer

The best way to understand it is to sit with a pencil and paper and trace the code through with some example data. Pencil and paper tracing of code execution seems to be a lost art these days...

 

[MythicFrost]

Right o, good idea, I'll give that a shot. I might use a text document and keyboard though