• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1814
  • Last Modified:

c / c++ implement a function that prints all possible combinations of the characters in a string

I;m trying to make a program to:
implement a function that prints all possible combinations of the characters in a string.these combinations range in length from one to the length of the string.2 combinations range in length from one 2 the length of the string.2 combinations that differ only in ordering of their characters r the same combination .in other words,"12" and "31" r different combinations from the input string "123",but "21" is the same as "12".

this is not homework, i'm preparing for a job interview for grapecity...
so iif anyone can guide me please help me
0
shilpi84
Asked:
shilpi84
  • 4
  • 3
  • 3
  • +1
3 Solutions
 
Infinity08Commented:
Just generate all combinations, like in this code :

        http://www.codeproject.com/cpp/CombC.asp

And then you could sort them, and eliminate duplicates. For that, you could insert them into a set for example :

        http://www.cplusplus.com/reference/stl/set/

(that will eliminate duplicates automatically).
0
 
PaulCaswellCommented:
Are you sure about

"... but "21" is the same as "12" ..."

as this turns it into a simple to trivial solution.

Imagine there are 32 characters in the string. Assign one bit from a 32 bit word to each character in the string. If the bit is a zero the character is not present in the solution and vice-versa.

Now just count your number up from one (I expect a zero-length solution would be invalid) until it overflows. You are guaranteed to generate all combinations of zeros and ones and therefore a solution to your problem.

Paul
0
 
Infinity08Commented:
>> Imagine there are 32 characters in the string. Assign one bit from a 32 bit word to each character in the string. If the bit is a zero the character is not present in the solution and vice-versa.

I thought about that too, but what if there are double characters in the string ? Then you still need to eliminate duplicates.
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
PaulCaswellCommented:
>>...Then you still need to eliminate duplicates.
Good point, but couldnt that be done using a pre-pass on the original string?

Paul
0
 
Infinity08Commented:
>> Good point, but couldnt that be done using a pre-pass on the original string?

Also a good point heh ;)
0
 
henderbopsCommented:
PaulCaswell's solution seems best to me.. correct me if i'm wrong anyone..

- get the length of the string: eg 16 letters
- generate all numbers from 1 to 2^length of string - 1 in a loop: 1 to 2^16 - 1
    - write these numbers in binary: number 15 = 1111000000000000 (16bit word)
    - for every 1 in the bit pattern match it to the place in the string outputting these characters:
- e.g.: string = thisismystring! (16 chars) 1111001000000000 therefore output: "thism"
- do this until all the bits are 1 and you have the full string written out (end of the loop)
-eliminate all duplicates, by means of maybe a set

Please note if this has clarified it, I don't want credit for PaulCaswells solution.

Good luck.
0
 
PaulCaswellCommented:
Quite correct, except for the last stage.

>>-eliminate all duplicates, by means of maybe a set

This should be unnecessary. If the same character appears duplicated in the original string, remove them on a pre-pass.

Paul
0
 
shilpi84Author Commented:
i didn't understand a word you said Paul and henderbops i'm sorry i couldn't understand it even after your clarfication
please can you explain a little more
sorry i couldn't understand
thanks
0
 
henderbopsCommented:
for example say you have a string "hello"
the string length is 5 characters right?
so you would take 2^4 (2 to the power of length of string subtract 1)
2^ is the same as 2 x 2 x 2 x 2 which = 16 if I am not mistaken this is the target in your loop
so you could loop from 0 to 16 e.g.
for (int a=0, a < target, a++).. (target is the 16 value in the example above)
then you would take whatever number 'a' is and convert it to binary (If you are unfamiliar with binary, I suggest you read up on it)
you would then within the loop convert 'a' to binary, i.e. if a=3 binary = 11000 in 5 bits in binary binary
then you would take the source string "hello" and for every '1' bit in the binary pattern.. you would match that to the letter in the string for example 11000 in hello means you would output or store "he" as part of hello, do this until the loop ends..

as for ridding yourself of duplicates you could write a function to do this, which should not be too hard, or you could go about creating a 'set' with these, which would eliminate duplicates immediately, since sets do not allow duplicates..

Does this clarify it any further?
0
 
PaulCaswellCommented:
How about this:

"abc"

Three characters so count in binary from 1 to limit of 3 bits (7)

abc
001->c
010->b
011->bc
100->a
101->ac
110->ab
111->abc

"Paul"

Four characters ...

Paul
0001-l
0010-u
0011-ul
0100-a
0101-al
0110-au
0111-aul
1000-P
1001-Pl
1010-Pu
1011-Pul
1100-Pa
1101-Pal
1110-Pau
1111-Paul

Get the idea?

Paul
0
 
henderbopsCommented:
In my response just there, I miscalculated, it needs to be 31 not sixteen
i.e. 2^5 ("hello" = 5 chars) - 1
= 2 x 2 x 2 x 2 x 2 = 32 -1 = 31..

sorry about that
0

Featured Post

Upgrade your Question Security!

Add Premium security features to your question to ensure its privacy or anonymity. Learn more about your ability to control Question Security today.

  • 4
  • 3
  • 3
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now