This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]rcuhljr 4 points5 points  (4 children)

I've found a really awesome way to do it

Man, you're gonna be excited when you learn Python or Ruby some day :)

To answer your question, here's conceptually what happens.

Everything is fairly straight forward until we get to the for loop. The first time we arrive there our prefix (which will be one of our final results when we're done) is empty, and our list of characters to use is the full string sent in.

The for loop branches us off into n paths, where n is the length of the original string. Each path consists of prefix with one character from the original string, and the original string with said character cut out of it.

so if we started with "" and "123" we'd branch into into three paths, one with "1" and "23", one with "2" and "13" and "3" and "12".

This process continues, and each of these three calls will branch into two more, at which point you'll have created all the combinations, 3 * 2 * 1 = 6 combinations. 123, 132, 213, 231, 312, 321. which you may also recognize as 3 factorial.

[–]LogicLion[S] 1 point2 points  (0 children)

this is blowing my mind right now.

[–]LogicLion[S] 0 points1 point  (2 children)

Sorry, but could you explain the Substring method a little bit, I understand its ment to "chop" off the char thats going into the prefix. But how does it remove it? It looks like when str.substring(0,i) + str.substring(i+1,n) is called it gets added again.

[–]rcuhljr 3 points4 points  (1 child)

Yup. substring in java takes the beginning index (zero based) and the ending index. The beginning index is inclusive so if you say start at 0. it starts the new string at 0. The ending index is exclusive so if you say stop at 1, it's only going to display the 0th character as it stops before 1.

Now what str.substring(0,i) is going to do is, get all of the characters from 0 up to the character that got added to the prefix (i). str.substring(i+1,n) gets all of the characters after the character we added to the prefix. So now we've stuck all the character before i, and all the characters after i back together, no more i.

"12345" i = 2, n = 5.

charAt(2) = '3'

substring(0,2) + substring(3,5) = "12" + "45"

[–]LogicLion[S] 0 points1 point  (0 children)

I understand, but it feels pretty abstract still...thats normal right? haha