Answered # Algorithm for permutating a word

Featured Reply VernonDozier 2,218 Discussion Starter IndianaRonaldo -3 theguitarist alwaysLearning0 39 Featured Reply VernonDozier 2,218 Discussion Starter IndianaRonaldo -3 Discussion Starter IndianaRonaldo -3 Need some help with this Array. I am trying to get the sum of the even numbers and the sum of the odd numbers using a for each loop. I know the answers to what I am trying to achive are sum of even = 84 and the sum of ...

1

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.

0

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?

0

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.

0

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?

2

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.

0

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.

0

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

This question has already been answered. Start a new discussion instead.

Recommended Articles

When I execute this progammatically, I get a table with row heights much larger than when I do this manually.

Note : Sel is the Word.Selection object and the Clipboard contains an Excel Table.

```
public void AddClipboard()
{
Sel.PasteExcelTable(false,false, false);
var t = Sel.Tables[Sel.Tables.Count];
t.AutoFitBehavior(Word.WdAutoFitBehavior.wdAutoFitContent);
}
```

the function that I created to find the ...