wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> list the Combination of a string.
        
(Message started by: bbskill on Nov 29^th, 2007, 11:41pm)

Title: list the Combination of a string.
Post by bbskill on Nov 29^th, 2007, 11:41pm

For example, given aba, the output should be
aba, aab, baa. Note that it is not permutation.

Title: Re: list the Combination of a string.
Post by towr on Nov 30^th, 2007, 12:07am

In what way is it not permutation?

Title: Re: list the Combination of a string.
Post by bbskill on Nov 30^th, 2007, 3:45am

on 11/30/07 at 00:07:27, 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

Title: Re: list the Combination of a string.
Post by towr on Nov 30^th, 2007, 7:41am

They're the unique permutations.

Title: Re: list the Combination of a string.
Post by bbskill on Nov 30^th, 2007, 8:31am

on 11/30/07 at 07:41:46, towr wrote:

They're the unique permutations.

Yes. My solution is permutation + hash. I believe the better solution exists?

Title: Re: list the Combination of a string.
Post by Grimbal on Nov 30^th, 2007, 9:01am

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.

Title: Re: list the Combination of a string.
Post by SMQ on Nov 30^th, 2007, 9:17am

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

Title: Re: list the Combination of a string.
Post by programmer on Oct 28^th, 2008, 11:43pm

Can u enumerate the reversing after position y (last part) wd an eg? I didnt get that.

Title: Re: list the Combination of a string.
Post by SMQ on Oct 29^th, 2008, 6:21am

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

Title: Re: list the Combination of a string.
Post by programmer on Oct 29^th, 2008, 6:40am

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?

Title: Re: list the Combination of a string.
Post by programmer on Oct 29^th, 2008, 6:41am

as in a dictionary kinda thingy...............in lexicographic ordering

Title: Re: list the Combination of a string.
Post by programmer on Oct 29^th, 2008, 6:44am

@ SMQ

n a BIG THANK YOU for taking d pain to explain the step with stunning visuals................. ;D ;D ;D

Title: Re: list the Combination of a string.
Post by programmer on Oct 29^th, 2008, 7:30am

@ SMQ

can u answer my query above ? extension of function?

Title: Re: list the Combination of a string.
Post by SMQ on Oct 29^th, 2008, 8:15am

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

Title: Re: list the Combination of a string.
Post by hoogle on Oct 29^th, 2008, 8:26am

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

Title: Re: list the Combination of a string.
Post by SMQ on Oct 29^th, 2008, 8:38am

on 10/29/08 at 08:26:20, 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

Title: Re: list the Combination of a string.
Post by programmer on Oct 29^th, 2008, 11:14am

@ 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.

Title: Re: list the Combination of a string.
Post by SMQ on Oct 29^th, 2008, 11:31am

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

Title: Re: list the Combination of a string.
Post by programmer on Oct 29^th, 2008, 10:22pm

@ 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.

Title: Re: list the Combination of a string.
Post by SMQ on Oct 30^th, 2008, 5:32am

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

Title: Re: list the Combination of a string.
Post by hoogle on Oct 30^th, 2008, 10:35pm

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

Title: Re: list the Combination of a string.
Post by SMQ on Oct 31^st, 2008, 5:44am

on 10/30/08 at 22:35:47, 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? ;D

--SMQ

Title: Re: list the Combination of a string.
Post by Hippo on Oct 31^st, 2008, 8:11am

on 10/31/08 at 05:44:41, 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? ;D

--SMQ

I am surprised for how long you sustain :).

Title: Re: list the Combination of a string.
Post by SMQ on Oct 31^st, 2008, 8:38am

on 10/31/08 at 08:11:49, 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.

;D

(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

Title: Re: list the Combination of a string.
Post by mistaken_id on Sep 14^th, 2009, 2:23pm

on 10/30/08 at 05:32:12, SMQ wrote:

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

Title: Re: list the Combination of a string.
Post by SMQ on Sep 15^th, 2009, 5:58am

on 09/14/09 at 14:23:41, mistaken_id wrote:

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

You could simply cull all out-of-order outputs from the algorithm. I.e. change the first line of the loop to "if the first n characters are in increasing order output the first n characters." That would roughly double the runtime but not change the complexity.

More efficient would probably be to just loop through each length and list the combinations directly, as here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1234536570).

--SMQ