I need a little help with algorithm for my code.Given a word "abacus" i have the code to find all its anagrams but i need to include also the words that are smaller in length than the original word. That is, I wanna be able to list ABA,AAB,ACA....ABAC,ABCS....so on.
Thanking you in advance.
IndianaRonaldo -3 Light Poster
VernonDozier 2,218 Posting Expert Featured Poster
Dig out the old statistics book and look up how to calculate the number of permutations and combinations. There are several ways to approach it. Beware of duplicates. C++ make life much easier because it'll test for it. Look at STL. There are quite a few containers in it that can help. From a COMBINATIONS point of view, your best bet is to store things in alphabetical order. Makes it really easy to test for duplicates. Then when when you find all the possible unique subsets of letters, take all the permutations of those and add them to your bigger list.
IndianaRonaldo -3 Light Poster
Dig out the old statistics book and look up how to calculate the number of permutations and combinations. There are several ways to approach it. Beware of duplicates. C++ make life much easier because it'll test for it. Look at STL. There are quite a few containers in it that can help. From a COMBINATIONS point of view, your best bet is to store things in alphabetical order. Makes it really easy to test for duplicates. Then when when you find all the possible unique subsets of letters, take all the permutations of those and add them to your bigger list.
Thanks a lot for the reply.I was thinking along the same lines to.But finding the subsets of letters is what proves to be the problem.Do you have have something specific in mind for that?
theguitarist 0 Junior Poster in Training
So you want to produce all possible subsets from a parent set.
Each subset (when all are obtained),will either contain a particular element of the parent set or not contain it.
Can it be recursively solved it with the idea?
Something like,consider the 1st element of the set as that element.
Then call the function again to deal with the rest of the set except that element.
When the subsets are out,that will be one part of the answer and you will have to ADD the 1st element to each of the subsets to get the other part.
Maybe a function could be written to eliminate all duplicates.
There may be better ways to do whole thing though.
Hope I am not wrong.
alwaysLearning0 39 Junior Poster
Hi,
Dont worry about subset. First try to do permutation for a word.
If you can generate permutation of a word, then subset is really easy.
You can treat each substring as a word and generate permutation for that word, you can use std::set to get rid of duplicates.
So, again, try to generate permutation for a single word!!. Do you need to help to generate permutation for a single word?
VernonDozier 2,218 Posting Expert Featured Poster
Take the "word" ACBACBCAC (I'm using this "word" rather than a real one since it makes my point easier).
Alphabetize the letters...
AAABBCCCC
3 A's, 2 B's, 4 C's.
A "subset" is any number of A's (0 to 3 inclusive), any number of B's(0 to 2 inclusive), any number of C's (0 to 4 inclusive).
The number of subsets is therefore 4 times 3 time 5 = 60. Generate them all. A nice nested loop will suffice. A function to turn an ordered triplet into a string might be useful. So (2,2,3) would turn into "AABBCCC". So there are your subsets.
Now for the permutations. How many ways can you scramble "AABBCCC"? Well there are 2 + 2 + 3 = 7 slots altogether. There are (7 choose 2) = 21 ways to place the A's, then (5 choose 2) = 10 ways to place the B's. The C's fill in the leftover spots. So there are 21 times 10 = 210 ways to scramble "AAABBCC". Print them all out. Do the same for the other 59 combinations and you have all possible orderings of the original word and any subset.
Pencil and paper it for a while till you get a pattern you can work with, then turn it into a computer program.
IndianaRonaldo -3 Light Poster
Hi,
Dont worry about subset. First try to do permutation for a word.
If you can generate permutation of a word, then subset is really easy.
You can treat each substring as a word and generate permutation for that word, you can use std::set to get rid of duplicates.So, again, try to generate permutation for a single word!!. Do you need to help to generate permutation for a single word?
permutation of a word i have already done.It is the subsets that i want.
IndianaRonaldo -3 Light Poster
Take the "word" ACBACBCAC (I'm using this "word" rather than a real one since it makes my point easier).
Alphabetize the letters...
AAABBCCCC
3 A's, 2 B's, 4 C's.
A "subset" is any number of A's (0 to 3 inclusive), any number of B's(0 to 2 inclusive), any number of C's (0 to 4 inclusive).
The number of subsets is therefore 4 times 3 time 5 = 60. Generate them all. A nice nested loop will suffice. A function to turn an ordered triplet into a string might be useful. So (2,2,3) would turn into "AABBCCC". So there are your subsets.
Now for the permutations. How many ways can you scramble "AABBCCC"? Well there are 2 + 2 + 3 = 7 slots altogether. There are (7 choose 2) = 21 ways to place the A's, then (5 choose 2) = 10 ways to place the B's. The C's fill in the leftover spots. So there are 21 times 10 = 210 ways to scramble "AAABBCC". Print them all out. Do the same for the other 59 combinations and you have all possible orderings of the original word and any subset.
Pencil and paper it for a while till you get a pattern you can work with, then turn it into a computer program.
wow...thanks a lot.That helps.Subsets was the problem.I already have a function to scramble it.Thanks again. :)
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.