permutations and combinations

Z

zgfareed

The requirements for my program is to input a set of substrings and
the length of the resulting strings which must be a multiple of the
length of the substrings. I have written the following program which
only generates permutations of the inputted substrings which does not
allow for repititions which is required for the output. For eg. with
substrings ef gh jk generate efefef efghjk etc. I have included the
permutation part of my program.

<code/>


copy(subString.begin(),subString.end(),ostream_iterator<string>(cout,""));
cout << endl;
while (next_permutation(subString.begin(), subString.end()))
{

copy(subString.begin(),subString.end(),ostream_iterator<string>(cout,""));
cout << endl;
}
</code>

By the way I load my substrings into a vector which I have not shown
here. Any suggestions??
 
M

Mark P

The requirements for my program is to input a set of substrings and
the length of the resulting strings which must be a multiple of the
length of the substrings.

That's the input requirement, but what is it supposed to do?

I have written the following program which
only generates permutations of the inputted substrings which does not
allow for repititions which is required for the output.

What does this mean? Are you supposed to generate all permutations?
All combinations, allowing for repetition? Both? Describe clearly what
you need to do-- it will help us and help you.

For eg. with
substrings ef gh jk generate efefef efghjk etc. I have included the
permutation part of my program.

<code/>


copy(subString.begin(),subString.end(),ostream_iterator<string>(cout,""));
cout << endl;
while (next_permutation(subString.begin(), subString.end()))
{

copy(subString.begin(),subString.end(),ostream_iterator<string>(cout,""));
cout << endl;
}
</code>

1. A construction of the form:

X
while( Y)
X

where X is a statement or block of statements, is equivalent to the more
compact construction:

do
X
while( Y);

2. Your code doesn't do what you claim it does. It generates all
permutations lexicographically *at or after* the input permutation,
which may very well not be all permutations if the input vector is not
initially sorted.

3. Printing all combinations with repetition is possibly easier than
printing all permutations (except that there's no convenient standard
library function to do it for you). Try to approach the problem
recursively.

-Mark
 
J

j_depp_99

That's the input requirement, but what is it supposed to do?

I have written the following program which


What does this mean? Are you supposed to generate all permutations?
All combinations, allowing for repetition? Both? Describe clearly what
you need to do-- it will help us and help you.

For eg. with







1. A construction of the form:

X
while( Y)
X

where X is a statement or block of statements, is equivalent to the more
compact construction:

do
X
while( Y);

2. Your code doesn't do what you claim it does. It generates all
permutations lexicographically *at or after* the input permutation,
which may very well not be all permutations if the input vector is not
initially sorted.

3. Printing all combinations with repetition is possibly easier than
printing all permutations (except that there's no convenient standard
library function to do it for you). Try to approach the problem
recursively.

-Mark- Hide quoted text -

- Show quoted text -

The program needs to use a vector to input a set of substrings of the
same length and then generate all possible strings of the same length
using only the substrings given as input. for eg. with the input of:
6
ab cd ef
the resulting combinations should be
ababab ababcd abcdab etc....

Thanks for checking my program and yes it is wrong. I will try and use
a recursive method as you suggested to allow for repitions.
 
M

Mark P

The program needs to use a vector to input a set of substrings of the
same length and then generate all possible strings of the same length
using only the substrings given as input. for eg. with the input of:
6
ab cd ef
the resulting combinations should be
ababab ababcd abcdab etc....

Thanks for checking my program and yes it is wrong. I will try and use
a recursive method as you suggested to allow for repitions.

Post your efforts here and you'll get more help if needed. Good luck.

Mark
 
J

Jim Langston

The program needs to use a vector to input a set of substrings of the
same length and then generate all possible strings of the same length
using only the substrings given as input. for eg. with the input of:
6
ab cd ef
the resulting combinations should be
ababab ababcd abcdab etc....

Thanks for checking my program and yes it is wrong. I will try and use
a recursive method as you suggested to allow for repitions.

It sounds like you have a vector of strings, and want all the possible
permutations , but need to disgard any permutations which are not a total
length of the combined input strings.

It sounds like a usage of get_next_permutation (or whatever it's called) and
disgarding any with the wrong length.
 
M

Mark P

Jim said:
It sounds like you have a vector of strings, and want all the possible
permutations , but need to disgard any permutations which are not a total
length of the combined input strings.

It sounds like a usage of get_next_permutation (or whatever it's called) and
disgarding any with the wrong length.

That doesn't help. All permutations generated by the relevant standard
library functions will have the same length since all permutations will
contain all input strings.

The OP hasn't made it clear whether the specified total length is always
the sum of the lengths of the constituent strings. If so,
next_permutation will come in handy; if not, he will likely have to code
it himself. Again, a recursive implementation is probably the easiest
approach.

Mark
 
J

j_depp_99

That doesn't help. All permutations generated by the relevant standard
library functions will have the same length since all permutations will
contain all input strings.

The OP hasn't made it clear whether the specified total length is always
the sum of the lengths of the constituent strings. If so,
next_permutation will come in handy; if not, he will likely have to code
it himself. Again, a recursive implementation is probably the easiest
approach.

Mark- Hide quoted text -

- Show quoted text -

Thanks guys for your input. I did mention that the length of the
resulting permutations/ combinations must be an integer multiple of
the length of the inputted substrings. I have not come up with
anything better yet. My program only produces permutations of each
substring with no replicates. i.e I input 'ab cd ef' into a vector and
6 being the length of the results. The output I'm supposed to get
should be:
ababab ababcd ababef abcdab...etc.
My output is : " abcdef abefcd cdabef cdefab efabcd efcdab.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top