Help needed with permutation function.

This is a discussion on Help needed with permutation function. within the C++ Programming forums, part of the General Programming Boards category; This function will eventually calculate all the permutaions for a set of letter of n length. I'm stumped on whether ...

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    91

    Help needed with permutation function.

    This function will eventually calculate all the permutaions for a set of letter of n length. I'm stumped on whether to declare something as a string or a char or a char and a char *. Any help would be appreciated.

    Code:
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    char GETALLCOMBOZ(char charact,int num){
    
    char *myArr = new char[num+1];
    
    int numofperms;
    char comboz;
    bool booler = false;
    
        do {
        
            myArr[numofperms] = myArr[numofperms]+ 1;
          
            if (numofperms == num)
            {
             
            comboz = comboz.substr(0, num - 1)+ charact.substr(myArr[numofperms],  1);
             
            }
          
            else
            {
              
            comboz = comboz + charact.substr(myArr[numofperms],  1);
            
            }
            
            if(myArr[numofperms] != strlen(charact) + 1) 
            
            {
                                         
                if(numofperms!= num)
                    {
                    
                    numofperms = numofperms + 1;
                    
                    }
                    
                 else
                   {
                 
                   cout << comboz;
                   }
            
             else
             {
                
                if (numofperms == 1)
                
                    {
                  
                    booler = true;
                    }
               
                 else {
                
                    myArr[numofperms] = 0;
                 
                    numofperms = numofperms - 1;
                 
                    comboz = comboz.substr(0, numofperms - 1);
                    }
         
            }
            
            
            }while (booler != true);
            
            
            }

  2. #2
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    well .substr works on strings, but strlen() works on char *'s. The std::string equivilent to strlen() is s.length() or s.size(). Your code confused me, so I am just going to give you the stl style answer
    Code:
    #include<iostream>
    #include<string>
    #include<algorithm>
    
    void allperm(std::string s) {
    	std::sort(s.begin(),s.end());
    	do {
    		std::cout << s << std::endl;
    	} while(std::next_permutation(s.begin(),s.end()));
    }
    Good luck on strings longer than about 10 characters or so.

  3. #3
    Registered User
    Join Date
    Jun 2003
    Posts
    91
    Quote Originally Posted by grib
    well .substr works on strings, but strlen() works on char *'s. The std::string equivilent to strlen() is s.length() or s.size(). Your code confused me, so I am just going to give you the stl style answer
    Code:
    #include<iostream>
    #include<string>
    #include<algorithm>
    
    void allperm(std::string s) {
    	std::sort(s.begin(),s.end());
    	do {
    		std::cout << s << std::endl;
    	} while(std::next_permutation(s.begin(),s.end()));
    }
    Good luck on strings longer than about 10 characters or so.
    That doesn't give all combinations, for ex. for a string "asd" all combos would be

    aaa
    aas
    aad
    asa
    ada
    saa
    daa
    sss
    ssa
    .....
    .....
    etc....

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Then you should have said so. The topic title asks for permutations, but apparently you want combinations.

    Anyway, I think the most straightforward way to get all combinations is to get all letter sets (i.e. "aaa", "aas", "aad", "asd", "ssd", "sss", "sdd", "ddd", "add", and "ass") and then use Salem's next_permutation loop on each.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,422
    > and then use Salem's next_permutation loop on each.
    Hey, don't pin this on me
    <bart>I didn't do it</bart>

  6. #6
    Registered User
    Join Date
    Jun 2003
    Posts
    91
    This is an attempt at porting VB code, here's the VB code and my attempt at the C++. It does compile but not doing the job.

    Code:
    Private Sub command1_Click()
    
        BOOLER = False
      GETALLCOMBOZ charz, 3   ' 4 = number of character combinations to try
      
    End Sub
    
    Public Sub GETALLCOMBOZ(ByVal charact As String, _
                      ByVal num As Byte)
    
        ReDim myarray(num)
        Do While Not (BOOLER)
     
            myarray(numofperms) = myarray(numofperms) + 1
            If numofperms = num Then
                comboz = Left$(comboz, num - 1) + Mid$(charact, myarray(numofperms), 1)
             Else
                comboz = comboz + Mid$(charact, myarray(numofperms), 1)
            End If
            If myarray(numofperms) <> Len(charact) + 1 Then
                If numofperms <> num Then
                    numofperms = numofperms + 1
                 Else
                   Print #1, comboz
                End If
             Else
                If numofperms = 1 Then
                    BOOLER = True
                 Else
                    myarray(numofperms) = 0
                    numofperms = numofperms - 1
                    comboz = Left$(comboz, numofperms - 1)
                End If
            End If
        Loop
        Close #1
    
    End Sub


    Code:
    #include <iostream>
    #include <string>
    #include <conio.h>
    #include <fstream>
    
    using namespace std;
    
    char *GetAllCombinations(string charact,int num);
    
    int main(){
        
        GetAllCombinations("abcd",3);
        // for example  aaa, aab, aac, aad, aba, aca, ada, baa, caa, daa
    }
    
    
    
    char *GetAllCombinations(string charact,int num){
    // redim array to size num     
    char *myArr = new char[num];
    // init vars
    int numofperms = 0;
    string comboz;
    bool booler = false;
    // open file for writing too
    ofstream a_file ( "c:\\windows\\desktop\\comboz.txt" );
    // start combinations loop
    
        do {
            
            myArr[numofperms] = myArr[numofperms]+ 1;
            
            if (numofperms == num)
            { 
                  
            comboz = comboz.substr(0, num - 1)+ charact.substr(myArr[numofperms],  1);
            }
            else
            {
            comboz = comboz + charact.substr(myArr[numofperms],  1);
           
            }
           
            if(myArr[numofperms] != charact.length() + 1) 
            
            {
                 if(numofperms!= num)
                 {
                 numofperms = numofperms + 1;
                 }
                 else
                 {
                 cout << comboz;
                 a_file<< comboz ;
                 }
             }
             else
             {
                 if (numofperms == 1)
                 {
                 booler = true;
                 }
                 else 
                 {
                 myArr[numofperms] = 0;
                 numofperms = numofperms - 1;
                 comboz = comboz.substr(0, numofperms - 1);
                 }
         
              }
            
            }while (booler != true);
            a_file.close();
    }
    If anybody could work out whats wrong with my C++ then cheers.

  7. #7
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    1. Code:
      char *GetAllCombinations(string charact,int num);
      You don't return anything, even though the function is declared to return a char*.
    2. Code:
      if(myArr[numofperms] != charact.length() + 1)
      Is that what you want? I see that's how it is in the VB code . . . .
    3. Code:
      myArr[numofperms] = myArr[numofperms]+ 1;
      ->
      Code:
      myArr[numofperms] ++;
      and
      Code:
      comboz = comboz + charact.substr(myArr[numofperms],  1);
      ->
      Code:
      comboz += charact.substr(myArr[numofperms],  1);
    4. Code:
      char *myArr = new char[num];
      You don't delete that memory.
    5. Code:
      #include <conio.h>
      That's non-standard, and besides you don't use it anywhere.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  8. #8
    Registered User
    Join Date
    Jun 2003
    Posts
    91
    Thanks for that reply your suggestions are useful.

    I'm not returning anything i'm printing the combination to a file during the loop. This is the part where it gets stuck on , gives an abnormal termination in command prompt,

    Code:
    if (numofperms == num)
            { 
                  
            comboz = comboz.substr(0, num - 1)+ charact.substr(myArr[numofperms],  1);
            }
            else
            {
            comboz = comboz + charact.substr(myArr[numofperms],  1);
           
            }
    does that code look ok. Been a while since i did any C++?
    Last edited by joeyzt; 01-07-2006 at 03:55 PM.

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    gives an abnormal termination in command prompt
    A segmentation fault, I'd guess. Because myArr isn't initialized to zero like you assume it to be.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Registered User
    Join Date
    Jun 2003
    Posts
    91
    Quote Originally Posted by dwks
    A segmentation fault, I'd guess. Because myArr isn't initialized to zero like you assume it to be.

    how do i do that ?

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Since myArr is an array of chars you can use memset. I would use a vector instead of a dynamic array, though, which allows you to initialize all values to 0 in the constructor.

  12. #12
    Registered User
    Join Date
    Jun 2003
    Posts
    91
    Quote Originally Posted by Daved
    Since myArr is an array of chars you can use memset. I would use a vector instead of a dynamic array, though, which allows you to initialize all values to 0 in the constructor.

    any chance of writing it, it must be nearly there ?

  13. #13
    Registered User
    Join Date
    Jun 2003
    Posts
    91
    groan... this is like pulling teeth..

    i thikn its this section here,

    Code:
    char GetAllCombinations(string charact,int num);
    
    int main(){
        
        GetAllCombinations("abcd",3);
        // for example  aaa, aab, aac, aad, aba, aca, ada, baa, caa, daa
    }
    
    
    char GetAllCombinations(string charact,int num){
    
    char *myArr = new char[num];  // think this is wrong
    
    int numofperms = 0;
    string comboz;        ' string or char ?
    bool booler = false;
    
    
        do {
            
            myArr[numofperms] ++;
            
            if (numofperms == num)
            { 
                  
            comboz = comboz.substr(0, num - 1)+ charact.substr(myArr[numofperms],  1);
            }
            else
            {
            comboz += charact.substr(myArr[numofperms],  1);
           
            }
    any thoughts?

  14. #14
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    groan... this is like pulling teeth..
    Welcome to programming.

    http://mathworld.wolfram.com/Combination.html

    Maybe this?

    http://paul.rutgers.edu/~rhoads/Code/code.html

  15. #15
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    And use delete.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

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

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. bit level permutation function
    By zxcv in forum C Programming
    Replies: 2
    Last Post: 07-27-2008, 01:26 PM
  3. In over my head
    By Shelnutt2 in forum C Programming
    Replies: 1
    Last Post: 07-08-2008, 06:54 PM
  4. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM
  5. Replies: 4
    Last Post: 11-23-2003, 06:15 AM

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