permutations and combinations

Discussion in 'C++' started by zgfareed@gmail.com, Sep 25, 2007.

  1. Guest

    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??
    , Sep 25, 2007
    #1
    1. Advertising

  2. Mark P Guest

    wrote:
    > 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
    Mark P, Sep 25, 2007
    #2
    1. Advertising

  3. Guest

    On Sep 25, 1:43 pm, Mark P <>
    wrote:
    > wrote:
    > > 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- 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.
    , Sep 25, 2007
    #3
  4. Mark P Guest

    wrote:
    > On Sep 25, 1:43 pm, Mark P <>
    > wrote:
    >> wrote:
    >>> 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- 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.
    >


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

    Mark
    Mark P, Sep 25, 2007
    #4
  5. Jim Langston Guest

    <> wrote in message
    news:...
    > On Sep 25, 1:43 pm, Mark P <>
    > wrote:
    >> wrote:
    >> > 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- 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.


    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.
    Jim Langston, Sep 26, 2007
    #5
  6. Mark P Guest

    Jim Langston wrote:
    > <> wrote in message
    > news:...
    >> On Sep 25, 1:43 pm, Mark P <>
    >> wrote:
    >>> wrote:
    >>>> 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- 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.

    >
    > 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
    Mark P, Sep 26, 2007
    #6
  7. Guest

    On Sep 25, 7:56 pm, Mark P <>
    wrote:
    > Jim Langston wrote:
    > > <> wrote in message
    > >news:...
    > >> On Sep 25, 1:43 pm, Mark P <>
    > >> wrote:
    > >>> wrote:
    > >>>> 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- 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.

    >
    > > 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- 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.
    , Sep 26, 2007
    #7
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jose luis fernandez diaz

    Combinations/permutations algorithm in C++

    jose luis fernandez diaz, Apr 13, 2004, in forum: C++
    Replies:
    6
    Views:
    14,089
    Leor Zolman
    Apr 13, 2004
  2. Alex Vinokur
    Replies:
    2
    Views:
    2,772
    Alex Vinokur
    May 13, 2004
  3. Jeff Kish

    permutations and combinations

    Jeff Kish, Mar 7, 2005, in forum: C++
    Replies:
    9
    Views:
    2,258
    DHOLLINGSWORTH2
    Mar 11, 2005
  4. Seth Leija

    Combinations or Permutations

    Seth Leija, Sep 20, 2010, in forum: Python
    Replies:
    4
    Views:
    255
    Raymond Hettinger
    Sep 21, 2010
  5. Peter Ensch
    Replies:
    5
    Views:
    190
Loading...

Share This Page