Like Tree3Likes

All the possible permutations of 'n' strings. C= n!/(n-k)! Possibly with 'n' ≠ 'k'

This is a discussion on All the possible permutations of 'n' strings. C= n!/(n-k)! Possibly with 'n' ≠ 'k' within the C++ Programming forums, part of the General Programming Boards category; Hello, I'm trying to make a program that prints all the possible permutations of some strings, where order matters and ...

  1. #1
    Registered User
    Join Date
    Jun 2013
    Posts
    2

    All the possible permutations of 'n' strings. C= n!/(n-k)! Possibly with 'n' ≠ 'k'

    Hello, I'm trying to make a program that prints all the possible permutations of some strings, where order matters and so following the formula: C= n!/(n-k)!.
    Now, I have this code with which I can have all the permutations, but not for "n" different from "k", what instead I'm actually looking for.
    Here is the code:

    Code:
    #include <iostream> // std::cout
    #include <algorithm> // std::next_permutation, std::sort
    #include <string> // std::string
    #include <vector> // std::vector
    
    int main () {
    
      std::string sentence1 = " A Sentence number one ";  
      std::string sentence2 = " B Sentence number two ";  
      std::string sentence3 = " C Sentence number three ";  
      std::string sentence4 = " D Sentence number four ";  
    
    // Store all the elements in a container ( here a std::vector)  
      std::vector<std::string> myVectorOfStrings;        
    
    // In the vector we add all the sentences.  
    // Note : It is possible to do myVectorOfStrings.push_back("Some sentence");  
      myVectorOfStrings.push_back(sentence1);  
      myVectorOfStrings.push_back(sentence2);  
      myVectorOfStrings.push_back(sentence3);  
      myVectorOfStrings.push_back(sentence4);  
    
    // The elements must be sorted to output all the combinations  
      std::sort (myVectorOfStrings.begin(),myVectorOfStrings.end());  
    
      std::cout << "The 4! possible permutations with 4 elements:\n"; 
    
      do {   
    
     //This printing can be improved to handle any number of sentences, not only four.  
      std::cout << myVectorOfStrings[0] << ' ' << myVectorOfStrings[1] << ' ' << myVectorOfStrings[2] << ' ' << myVectorOfStrings[3] << '\n'; 
    
      } while ( std::next_permutation(myVectorOfStrings.begin(),myVectorOfStrings.end()) );  
    
      std::cout << "After loop: "  << myVectorOfStrings[0] << ' ' << myVectorOfStrings[1] << ' ' << myVectorOfStrings[2] << ' ' << myVectorOfStrings[3] << '\n'; 
    
      return 0;
    }


    Sorry if I make this message even longer, but just to clarify, that is an example of what I'm having:


    Code:
    1) string1 string2 string3 string4 string5 string6 string7 string8 string9 string10 
    2) string1 string2 string3 string4 string5 string6 string7 string8 string10 string9 
    3) string1 string2 string3 string4 string5 string6 string7 string9 string8 string10 
    4) string1 string2 string3 string4 string5 string6 string7 string9 string10 string8 ....
    while that is the kind of thing I'm trying to obtain:

    Code:
    1)  string1 string2 string3 string4 string5 
    2)  string1 string2 string3 string4 string6 
    3)  string1 string2 string3 string4 string7 
    4)  string1 string2 string3 string4 string8 
    5)  string1 string2 string3 string4 string9 
    6)  string1 string2 string3 string4 string10 
    7)  string1 string2 string3 string5 string4 
    8)  string1 string2 string3 string5 string6 
    9)  string1 string2 string3 string5 string7 
    10) string1 string2 string3 string5 string8 
    11) string1 string2 string3 string5 string9 
    12) string1 string2 string3 string5 string10....
    As you can see, in the first one n=10 and k=10; in the second, n=10 but k=5 (5 "spaces").

    Thank you in advance!
    Last edited by user2988; 06-22-2013 at 11:16 AM.

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    You need to add the code to do combinations. You can try to figure this out for yourself, or do a web search for "next combination", or I can post example code if you still need help.

  3. #3
    Registered User
    Join Date
    Jun 2013
    Posts
    2
    Thank you for the reply, an example would be very helpful.

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    Example code to do all combinations and permutations for n integers 0 to n-1. In this example, doc() generates the combinations, dop() generates the permutations, and showp() displays a permutation of integers. Change or replace the code to use the integers as indexes to the strings. This is C code, but easily converted to C++.

    Code:
    #include <stdio.h>
    #include <malloc.h>
    
    /* set to 0 to do only combinations */
    #define DOPERM 1
    
    static int n = 5;                       /* n integers */
    static int k;                           /* taken k at a time */
    
    static int *c;                          /* combinations */
    static int *p;                          /* permutations */
    
    static void doc(void);
    static void dop(void);
    static void swap(int, int);
    static void showp(void);
    
    /*----------------------------------------------------------------------*/
    /*      main                                                            */
    /*----------------------------------------------------------------------*/
    int main(int argc, char *argv[])
    {
        c = malloc(n *  sizeof(int));       /* allocate arrays */
        p = malloc(n *  sizeof(int));
    
        for(k = 1; k <= n; k++)             /* n things k at a time */
            doc();
     
        free(p);                            /* free arrays */
        free(c);
    
        return(0);                          /* return */
    }
    
    /*----------------------------------------------------------------------*/
    /*      doc         do combinations                                     */
    /*----------------------------------------------------------------------*/
    static void doc()
    {
    int i, j;
    
        for (i = 0; i < k;  i++)            /* generate initial combination */
            c[i] = i;
    
        dop();                              /* do permutations */
    
        while(1)                            /* generate next combination */
        {       
            i = k-1;                        /* find next element to increment */
            while(c[i] == (n-k+i))
                --i;
            if (i < 0)                      /* return if done */
                return;
            ++c[i];                         /* increment element */
    
            for(j = i+1; j < k; j++)        /* create increasing string */
                c[j] = c[i]+j-i;
    
            dop();                          /* do permutations */
        }
    }
    
    /*----------------------------------------------------------------------*/
    /*      dop         do permutations                                     */
    /*----------------------------------------------------------------------*/
    static void dop()
    {
    int i;
    #if DOPERM
    int j;
    #endif
    
        for (i = 0; i < k;  i++)            /* initial perm = comb */
            p[i] = c[i];
        printf("\n");
        showp();                            /* show permutation */
    
    #if DOPERM
    
        if(k < 2)                           /* return if only 1 element */
            return;
    
        while(1)                            /* generate next permutation */
        {
    
    /*      scan backwards as long as p[] order is reversed */
        
            i = k-2;                        /* scan backwards until */
            while(p[i] >= p[i+1])           /* p[i] < p[i+1] */
                i--;
            if (i < 0)                      /* return if done (all reversed) */
                return;
    
    /*      p[i] is left most integer to swap */
    /*      scan from right end until p[j] > p[i] is found */
    
            j = k-1;                        /* scan backwards until */
            while (p[j] <= p[i])            /* p[j] > p[i] */
                j--;
    
    /*      p[j] is right most integer to swap */
    
            swap(i, j);                     /* swap elements */
    
    /*      reverse p[] from p[i+1] to p[k-1] */
    
            i++;                            /* reverse elements */
            j = k-1;
            while (i < j)
            {
                swap(i, j);
                i++;
                j--;
            }
    
            showp();                        /* show permutation */
        }
    #endif                                  /* #if DOPERM */
    }
    
    /*----------------------------------------------------------------------*/
    /*      swap two elements of p                                          */
    /*----------------------------------------------------------------------*/
    static void swap(int i, int j)
    {
    int temp;
    
        temp = p[i];
        p[i] = p[j];
        p[j] = temp;
    }
    
    /*----------------------------------------------------------------------*/
    /*      showp       show permutation                                    */
    /*----------------------------------------------------------------------*/
    static void showp(void)
    {
    int i;
    
        for (i = 0; i < k; i++)
            printf(" %1d", p[i]);
        printf("\n");
    }

  5. #5
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    That's a pretty long example. I have a feeling a more minimal example would have been better.
    It also does not do any justice in that it uses global arrays and malloc and free where C++ would not.
    I can understand you want to show an example you would have lying around (if you wrote it from scratch, it really should be in C++), but this is a little extreme. It focuses on too much C than C++ alternatives, drawing a lot of attention from the logic to maintaining the correctness in the code due to low-level code.
    rogster001 likes this.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    Quote Originally Posted by Elysia View Post
    That's a pretty long example.
    The only code needed to be added to get combinations is this part. I added input parameters for this version (I think the syntax is correct, c should be a reference to an integer array).

    Code:
    /*----------------------------------------------------------------------*/
    /*      doc         do combinations                                     */
    /*----------------------------------------------------------------------*/
    static void doc(int (&c)[], int k, int n)
    {
    int i, j;
    
        for (i = 0; i < k;  i++)            /* generate initial combination */
            c[i] = i;
    
        dop();                              /* do permutations */
    
        while(1)                            /* generate next combination */
        {       
            i = k-1;                        /* find next element to increment */
            while(c[i] == (n-k+i))
                --i;
            if (i < 0)                      /* return if done */
                return;
            ++c[i];                         /* increment element */
    
            for(j = i+1; j < k; j++)        /* create increasing string */
                c[j] = c[i]+j-i;
    
            dop();                          /* do permutations */
        }
    }
    Last edited by rcgldr; 06-22-2013 at 05:30 PM.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    Quote Originally Posted by rcgldr View Post
    The only code needed to be added to get combinations is this part. I added input parameters for this version (I think the syntax is correct, c should be a reference to an integer array).
    Correction, c should be a pointer to integer.

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    Some braces are missing from the code above on the while loops that include check for i < 0. Here's the fixed code for the combination function doc():

    Code:
    //----------------------------------------------------------------------//
    //      doc         do combinations                                     //
    //----------------------------------------------------------------------//
    static void doc(int *c, int k, int n)
    {
    int i, j;
    
        for (i = 0; i < k;  i++)            // generate initial combination
            c[i] = i;
    
        dop(c, k);                          // do permutations
    
        while(1)                            // generate next combination
        {
            i = k-1;                        // find next element to increment
            while(c[i] == (n-k+i)){
                --i;
                if (i < 0)                  // return if done
                    return;
            }
            ++c[i];                         // increment element
    
            for(j = i+1; j < k; j++)        // create increasing string
                c[j] = c[i]+j-i;
    
            dop(c, k);                      // do permutations
        }
    }

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    Example program:

    Code:
    //----------------------------------------------------------------------//
    //      cmbprmv.cpp  combinations and permutations example              //
    //----------------------------------------------------------------------//
    #include <algorithm>
    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    int next_combination(vector <int> &, int, int);
    
    //----------------------------------------------------------------------//
    //      main                                                            //
    //----------------------------------------------------------------------//
    int main(int argc, char **argv)
    {
    string s = "string x";                  // numbered string
    int n = 4;                              // n things k at a time
    int i, k;
    
        vector <string> vs(n);              // create vector of strings
        for(i = 0; i < n; i++){
            s[s.size()-1] = '0'+i;
            vs[i] = s;
        }
    
        vector <int> c(n);                  // combination array
    
        for(k = 1; k <= n; k++){            // n things k at a time
            for(i = 0; i < k;  i++)         // create initial combination
                c[i] = i;
            do{                             // do combination
                do{                         //    do permutation
                    for(i = 0; i < k; i++)
                        cout << vs[c[i]] << " ";
                    cout << endl;
                }
                while(next_permutation(c.begin(), c.end()));
            cout << endl;
            }
            while(next_combination(c, k, n));
        }
    
        return(0);
    }
    
    //----------------------------------------------------------------------//
    //      next_combination                                                //
    //----------------------------------------------------------------------//
    int next_combination(vector <int> &c, int k, int n)
    {
    int i, j;
    
        i = k-1;                            // find next element to increment
        while(c[i] == (n-k+i)){
            --i;
            if (i < 0)                      // return if done
                return(0);
        }
    
        c[i] += 1;                          // increment element
    
        for(j = i+1; j < k; j++)            // create increasing string
                c[j] = c[i]+j-i;
    
        return(1);                          // return with new combination
    }

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    Fixed the example program (the parameters passed to next_permutation()). Updated next_combination() to set initial combination when done, similar to next_permutation() which sets the original permutation when done.

    Code:
    //----------------------------------------------------------------------//
    //      cmbprmv.cpp  combinations and permutations example              //
    //----------------------------------------------------------------------//
    #include <algorithm>
    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    int next_combination(vector <int> &, int, int);
    
    //----------------------------------------------------------------------//
    //      main                                                            //
    //----------------------------------------------------------------------//
    int main(int argc, char **argv)
    {
    string s = "string x";                  // numbered string
    int n = 4;                              // n things k at a time
    int i, k;
    
        vector <string> vs(n);              // create vector of strings
        for(i = 0; i < n; i++){
            s[s.size()-1] = '0'+i;
            vs[i] = s;
        }
    
        vector <int> c(n);                  // combination array
    
        for(k = 1; k <= n; k++){            // n things k at a time
            for(i = 0; i < k;  i++)         // create initial combination
                c[i] = i;
            do{                             // do combination
                do{                         //    do permutation
                    for(i = 0; i < k; i++)
                        cout << vs[c[i]] << " ";
                    cout << endl;
                }
                while(next_permutation(c.begin(), c.begin()+k));
            cout << endl;
            }
            while(next_combination(c, k, n));
        }
    
        return(0);
    }
    
    //----------------------------------------------------------------------//
    //      next_combination                                                //
    //----------------------------------------------------------------------//
    int next_combination(vector <int> &c, int k, int n)
    {
    int i, j;
    
        i = k-1;                            // find next element to increment
        while(c[i] == (n-k+i)){
            --i;
            if (i < 0){                     // if done, ...
                for(i = 0; i < k;  i++)
                    c[i] = i;
                return(0);                  // ... return with initial combination
            }
        }
    
        c[i] += 1;                          // increment element
    
        for(j = i+1; j < k; j++)            // create increasing string
                c[j] = c[i]+j-i;
    
        return(1);                          // return with new combination
    }
    Last edited by rcgldr; 06-23-2013 at 09:27 AM.

  11. #11
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    Four posts in a row without any input from the OP. Surely the OP should be able to experiment a little with the code and returning with success or questions before you do all the work for him/her?
    phantomotap likes this.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  12. #12
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,802
    Surely the OP should be able to experiment a little with the code and returning with success or questions before you do all the work for him/her?
    O_o

    I wonder what response we will get this time:

    1): I know this is not homework, so posting complete solutions isn't a problem.
    2): Posting complete solutions is how it is done at other forums I visit.
    3): I don't value other people's education.

    I'm thinking #4: all of the above.

    Soma

  13. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    Quote Originally Posted by Elysia View Post
    That's a pretty long example. ... not C++ ... a more minimal example would have been better.
    Quote Originally Posted by Elysia View Post
    Four posts in a row without any input from the OP. Surely the OP should be able to experiment a little with the code and returning with success or questions before you do all the work for him/her?
    The OP's code just uses next_permutation(), it's not like he's writing his own permutation code, and the OP could have just done a web search as I suggested to find a next_combination() function almost identical to the one I wrote, but the OP asked for example code.

    I was just trying to create a minimal example (as you mentioned) of a C++ next_combination() function similar to the next_permutation() function that the OP uses in his code, except I'm not aware how to implement a generic next_combination() function that doesn't require a sequential sequence of integers 0 to n-1.

    Sorry it took four posts to get it right. two of those posts were from intermediate and faulty versions where I copied to make a backup in the wrong direction in one or both cases and didn't notice this until it was too late to edit. I was tired and busy with other stuff. Next time I'll just wait a day when I have the proper amount of time to get it right before posting anything.

  14. #14
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    No one expects you to write bug-free code. No one expects you to post perfect code.
    In fact, if you even embed some bugs in your code, it could serve as an exercise to the OP to find and fix them. I'm just saying it seems like you are throwing too much at the OP with too little sign of effort from the OP's side. Remember that we are also answering for their sake.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  15. #15
    Registered User
    Join Date
    Apr 2013
    Posts
    1,161
    Quote Originally Posted by Elysia View Post
    No one expects you to write bug-free code. No one expects you to post perfect code. In fact, if you even embed some bugs in your code, it could serve as an exercise to the OP to find and fix them. I'm just saying it seems like you are throwing too much at the OP with too little sign of effort from the OP's side. Remember that we are also answering for their sake.
    OK, again I'm used to standard from another forum (physics forum). So when posting here, even when it's not homework, I should always ignore requests for example code until the OP has shown some effort to produce the code on his/her own and only post hints or corrections?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help needed with strings permutations program
    By anujit1601 in forum C Programming
    Replies: 6
    Last Post: 08-15-2012, 12:15 PM
  2. Permutations
    By bumfluff in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2008, 12:33 PM
  3. Could someone possibly take a look at this?
    By Joe123 in forum C++ Programming
    Replies: 5
    Last Post: 03-01-2006, 08:39 PM
  4. Replies: 9
    Last Post: 01-21-2004, 03:53 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21