Author |
Topic: list the Combination of a string. (Read 3414 times) |
|
bbskill
Newbie
Posts: 42
|
 |
list the Combination of a string.
« on: Nov 29th, 2007, 11:41pm » |
 Quote  Modify
|
For example, given aba, the output should be
aba, aab, baa. Note that it is not permutation.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: list the Combination of a string.
« Reply #1 on: Nov 30th, 2007, 12:07am » |
Quote Modify
|
In what way is it not permutation?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
bbskill
Newbie
Posts: 42
|
|
Re: list the Combination of a string.
« Reply #2 on: Nov 30th, 2007, 3:45am » |
Quote Modify
|
on Nov 30th, 2007, 12:07am, towr wrote:| In what way is it not permutation? |
|
for example, the given string is aaa.
the permutation are six aaa, but the combination is just one aaa.
if the string is aba. because the string has two a, so the permutation are
aba --- first a, b, second a.
aba --- second a, b, first a.
baa
baa
aab
aab.
but the combination are
aba
baa
aab
|
| « Last Edit: Nov 30th, 2007, 3:49am by bbskill » |
IP Logged |
|
|
|
bbskill
Newbie
Posts: 42
|
|
Re: list the Combination of a string.
« Reply #4 on: Nov 30th, 2007, 8:31am » |
Quote Modify
|
on Nov 30th, 2007, 7:41am, towr wrote:| They're the unique permutations. |
|
Yes. My solution is permutation + hash. I believe the better solution exists?
|
| « Last Edit: Nov 30th, 2007, 8:48am by bbskill » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: list the Combination of a string.
« Reply #5 on: Nov 30th, 2007, 9:01am » |
Quote Modify
|
First, collect the different characters and count them, then generate the permutations recursively by adding one by one each of the characters you haven't used up.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: list the Combination of a string.
« Reply #6 on: Nov 30th, 2007, 9:17am » |
Quote Modify
|
There's a standard algorithm for this (which works fairly efficiently whether or not there are duplicates) credited to Dijkstra:
Repeat:
Find the last element less than the element following it
If there is no such element, reverse the entire list
Otherwise:
Call this element x
Find the last element greater than x, call this element y
Swap x and y
Reverse all elements after the position in which x was found (where y is now)
Until you reach the permutation you started with.
This will enumerate all unique permutations in lexicographical order (one at the start/end of each pass through the loop).
--SMQ
|
| « Last Edit: Nov 30th, 2007, 9:24am by SMQ » |
IP Logged |
--SMQ
|
|
|
programmer
Newbie
Posts: 32
|
|
Re: list the Combination of a string.
« Reply #7 on: Oct 28th, 2008, 11:43pm » |
Quote Modify
|
Can u enumerate the reversing after position y (last part) wd an eg? I didnt get that.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: list the Combination of a string.
« Reply #8 on: Oct 29th, 2008, 6:21am » |
Quote Modify
|
Start with a string:
ABEHGFDC
> Find the last element less than the element following it
ABEHGFDC
^
> Call this element x
ABEHGFDC
^
x
> Find the last element greater than x, call this element y
ABEHGFDC
^ ^
x y
> Swap x and y
ABFHGEDC
^ ^
y x
> Reverse all elements after the position in which x was found (where y is now)
ABFCDEGH
^
y
Clear?
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
programmer
Newbie
Posts: 32
|
|
Re: list the Combination of a string.
« Reply #9 on: Oct 29th, 2008, 6:40am » |
Quote Modify
|
ya ya, i got it.
can v extend this procedure to include cases wherein a string is accepted by a user n all possible strings in order (starting from single letter alphabets, then double letter etc) can b printed?
|
|
IP Logged |
|
|
|
programmer
Newbie
Posts: 32
|
|
Re: list the Combination of a string.
« Reply #10 on: Oct 29th, 2008, 6:41am » |
Quote Modify
|
as in a dictionary kinda thingy...............in lexicographic ordering
|
|
IP Logged |
|
|
|
programmer
Newbie
Posts: 32
|
|
Re: list the Combination of a string.
« Reply #11 on: Oct 29th, 2008, 6:44am » |
Quote Modify
|
@ SMQ
n a BIG THANK YOU for taking d pain to explain the step with stunning visuals................. 
|
| « Last Edit: Oct 29th, 2008, 6:45am by programmer » |
IP Logged |
|
|
|
programmer
Newbie
Posts: 32
|
|
Re: list the Combination of a string.
« Reply #12 on: Oct 29th, 2008, 7:30am » |
Quote Modify
|
@ SMQ
can u answer my query above ? extension of function?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: list the Combination of a string.
« Reply #13 on: Oct 29th, 2008, 8:15am » |
Quote Modify
|
If you can have the lengths intermixed, then it's easy to do using using the algorithm:
- Start by sorting the string, then output each substring from the start:
A
AB
ABC
ABCD
ABCDE
ABCDEF
ABCDEFG
ABCDEFGH
- After each step of the permutation algorithm, output each substring (from the start) involving the changed elements, so after the example I gave above:
ABF
ABFC
ABFCD
ABFCDE
ABFCDEG
ABFCDEGH
- Stop (without outputting anything) when you would need to reverse the entire string
That would print every substring of the given string in dictionary order, for example, if the user typed CAB, you would get the following (permutations in yellow, output in orange):
ABC A
AB
ABC
ACB AC
ACB
BAC B
BA
BAC
BCA BC
BCA
CAB C
CA
CAB
CBA CB
CBA
If you need the lengths separated, I think you'll need to make one pass through the permutation algorithm for each length, only outputting strings of the appropriate length. You could speed these up by always choosing x to be in the first n characters of the string: i.e. the first step of the algorithm becomes "Find the last element of the first n less than the element following it" (for output of length n).
--SMQ
|
| « Last Edit: Oct 29th, 2008, 8:20am by SMQ » |
IP Logged |
--SMQ
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: list the Combination of a string.
« Reply #14 on: Oct 29th, 2008, 8:26am » |
Quote Modify
|
Quote:| can v extend this procedure to include cases wherein a string is accepted by a user n all possible strings in order (starting from single letter alphabets, then double letter etc) can b printed? |
|
We can generate all the combinations of the string in lexicographic order.... and at each point when we get a combination send it to the permutation function that SMQ has given.......That generates all the permutations in lexicographic order and also with increasing lengths
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: list the Combination of a string.
« Reply #15 on: Oct 29th, 2008, 8:38am » |
Quote Modify
|
on Oct 29th, 2008, 8:26am, hoogle wrote:| That generates all the permutations in lexicographic order and also with increasing lengths |
|
No, it doesn't; permuting a substring before examining the next combination can give out-of-order results (in red):
A
B
C
AB
BA
AC
CA
BC
CB
ABC
ACB
BAC
BCA
CAB
CBA
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
programmer
Newbie
Posts: 32
|
|
Re: list the Combination of a string.
« Reply #16 on: Oct 29th, 2008, 11:14am » |
Quote Modify
|
@ SMQ
i still don't understand what you're tryin to say.
Plz explain clearly.
For ABCD i want this output :
A
B
C
D
AB
AC
AD
BA
BC
BD
CA
CB
CD
DA
DB
DC
ABC
ABD
...
..
..
plz help.
|
| « Last Edit: Oct 29th, 2008, 10:31pm by programmer » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: list the Combination of a string.
« Reply #17 on: Oct 29th, 2008, 11:31am » |
Quote Modify
|
Given: a user-input string of length L
Sort the characters of the string
For each n from 1 to L
Repeat:
Output the first n characters
Find the last character of the first n which is less than the character following it, call this character x
Find the last character greater than character x, call this character y
Swap characters x and y
Reverse all characters after the position in which x was found (where y is now)
Until the string is sorted
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
programmer
Newbie
Posts: 32
|
|
Re: list the Combination of a string.
« Reply #18 on: Oct 29th, 2008, 10:22pm » |
Quote Modify
|
@ SMQ
Suppose user enters DBAC
Sorted string ABCD
for n = 1
print A (first n characters)
select A (x) (last of first 1 characters less than characters following it)
select D (last char > A)
swap A & D
string becomes DBCA
reverse after A's old position
string becomes DACB
now loop iterates again
print first n characters i.e. D is printed
havent we got wrong results ?
after A, B shud have been printed but v got D.
|
| « Last Edit: Oct 29th, 2008, 10:25pm by programmer » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: list the Combination of a string.
« Reply #19 on: Oct 30th, 2008, 5:32am » |
Quote Modify
|
Yeah, sorry, my "shortcut" doesn't quite work -- I missed a step:
Sort the characters of the string
For each n from 1 to L
Repeat:
Output the first n characters
Reverse all characters after position n
Find the last character of the first n which is less than the character following it, call this character x
Find the last character greater than character x, call this character y
Swap characters x and y
Reverse all characters after the position in which x was found (where y is now)
Until the string is sorted
There are some improvements that can be made for efficiency (to avoid the double-reversing at every pass), but I think the above is the easiest to understand: the net effect of all the "skipped" steps in the shortcut is to reverse all the characters after position n, so we need to do that explicitly.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: list the Combination of a string.
« Reply #20 on: Oct 30th, 2008, 10:35pm » |
Quote Modify
|
Quote:Yeah, sorry, my "shortcut" doesn't quite work -- I missed a step:
Sort the characters of the string
For each n from 1 to L
Repeat:
Output the first n characters
Reverse all characters after position n
Find the last character of the first n which is less than the character following it, call this character x
Find the last character greater than character x, call this character y
Swap characters x and y
Reverse all characters after the position in which x was found (where y is now)
Until the string is sorted
There are some improvements that can be made for efficiency (to avoid the double-reversing at every pass), but I think the above is the easiest to understand: the net effect of all the "skipped" steps in the shortcut is to reverse all the characters after position n, so we need to do that explicitly.
|
|
Is there any other step you forgot, like what if we cannot any x in first n elements?
where x is the last element which is less than its neighbor
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: list the Combination of a string.
« Reply #21 on: Oct 31st, 2008, 5:44am » |
Quote Modify
|
on Oct 30th, 2008, 10:35pm, hoogle wrote:| like what if we cannot any x in first n elements? |
|
Then you're done with that n: reverse the whole string and go to the next n.
Sheesh, do I really need to spell out every little step like it's a computer program or something?
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: list the Combination of a string.
« Reply #22 on: Oct 31st, 2008, 8:11am » |
Quote Modify
|
on Oct 31st, 2008, 5:44am, SMQ wrote:
Then you're done with that n: reverse the whole string and go to the next n.
Sheesh, do I really need to spell out every little step like it's a computer program or something?
--SMQ |
|
I am surprised for how long you sustain  .
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: list the Combination of a string.
« Reply #23 on: Oct 31st, 2008, 8:38am » |
Quote Modify
|
on Oct 31st, 2008, 8:11am, Hippo wrote:| I am surprised for how long you sustain . |
|
Well, it's a very welcoming forum; there are no stupid questions here, only stupid people, and it's my job as a moderator to lead them on until they realize just how clueless they really are...wait, no, that's not right, let me try that again:
There are no stupid questions here, only stupid moderators who can't recognize a lost cause when they see one. Yeah, that's it.
(For the humor impaired, yes, I'm kidding; no, I don't mind answering seemingly-simple questions from people without much experience -- I figure it's part of what we're here for -- sometimes the teacher, sometimes the student.)
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: list the Combination of a string.
« Reply #24 on: Sep 14th, 2009, 2:23pm » |
Quote Modify
|
on Oct 30th, 2008, 5:32am, SMQ wrote:Yeah, sorry, my "shortcut" doesn't quite work -- I missed a step:
Sort the characters of the string
For each n from 1 to L
Repeat:
Output the first n characters
Reverse all characters after position n
Find the last character of the first n which is less than the character following it, call this character x
Find the last character greater than character x, call this character y
Swap characters x and y
Reverse all characters after the position in which x was found (where y is now)
Until the string is sorted
There are some improvements that can be made for efficiency (to avoid the double-reversing at every pass), but I think the above is the easiest to understand: the net effect of all the "skipped" steps in the shortcut is to reverse all the characters after position n, so we need to do that explicitly.
--SMQ |
|
Is there a way to extend this algorithm to print only combinations of strings.
For example; given an input "abc"
It should print
a
b
c
ab
ac
bc
abc
Lexicographic order of combinations.........
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print