Help please

This is a discussion on Help please within the C++ Programming forums, part of the General Programming Boards category; I'm trying to write a function :void permutations(int m,int n) to print all the permutations of the numbers 1,...,m per ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    27

    Help please

    I'm trying to write a function :void permutations(int m,int n) to print all the permutations of the numbers 1,...,m per n.For example , permutations(4,2) should print:
    (1,2)
    (1,3)
    (1,4)
    (2,1)
    (2,3)
    (2,4)
    (3,1)
    (3,2)
    (3,4)
    (4,1)
    (4,2)
    (4,3)

    I've tried many things with no results.Can you help me?
    Recursive and non-recursive functions are both acceptable.

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    1,109
    code?

    and code tags...

    no we won't write the program for you, but we are glad to help you with trouble you have.

  3. #3
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Its quite easily doable using recursion.

    You need to show us some code before we will help you though.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  4. #4
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    why is thge 2nd number needed thanb.. you just require 4 to generate it.. what is the job of 2 here.. is it saying 2 numbers or sometin...


    you can use a loop say
    the number is 3

    1,2
    1,3
    2,1
    2,3
    3,1
    3,2

    I am helping ytou because you seem new here.. never repeat the same mistake again of only askin questions... put some effort..



    the program would be..


    Code:
    # include <iostream.h>
    
    
    int main()
    {
    int num;
    cout<<"\n Enter the limit > ";
    cin>>num;
    
    for(int i=1;i<=num;i++)
    {
    
    for(int j=1;j<=num;j++)
             {
    if(i!=j)
                  {
                    cout<<i<<","<<j<<"\n";
                   }
    
             }
    
    }
    
    
    
    return 0;
    }

    this should do the work...

  5. #5
    Registered User
    Join Date
    Apr 2003
    Posts
    27
    I am new here indeed.But I tried some things with no result.
    Your program would be perfect if we knew from the start the numbers m and n in permutations(m,n),but we don't.I want the function to work for every pair m,n no matter how large they are.The second argument n is required.If we had :
    permutations(5,4) it should print:
    (1,2,3,4)
    (1,2,3,5)
    (1,2,4,3)
    (1,2,4,5)
    ...
    ...
    ...
    One thought i made was similar to yours but more general.I thought of making n nested for loops.But I also wanted inside the last nested loop to know all the values of the variables used in the above loops(i,j,k,...).I have no idea how to achieve this non-recursively.Do you?
    I tried to make it recursively something like that:

    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void permutations(int m,int n) {
        
        static vector<int> a(n);
        static int N=n;
        bool check=true;
        a[n-1]=n;
        for(int i=1;i<=m;i++)
            if(n==1) {
                for(int j=0;j<N-1;j++)
                    for(int k=j+1;k<N;k++)
                        if(a[j]==a[k]) check=false;
                if(check) {
                    cout<<'(';
                    for(int j=0;j<N;j++)
                        cout<<a[j]<<',';
                    cout<<')'<<endl;
                }
            }
            else permutations(m,n-1);
    }
    
    int main()
    {
    
    permutations(5,3);
    
     cin.get();
    
    }
    But the result is:

    (1,2,3,)
    (1,2,3,)
    (1,2,3,)
    (1,2,3,)
    (1,2,3,)
    ...

    Any helpful ideas?
    Last edited by k_w_s_t_a_s; 04-25-2003 at 08:51 AM.

  6. #6
    Registered User
    Join Date
    Apr 2003
    Posts
    27
    Something else:
    Why doesn't the post include the spaces i've put in my program?
    When i write it is ok,but when i post it all the spaces are eliminated.

  7. #7
    0x01
    Join Date
    Sep 2001
    Posts
    88
    Go here: http://cboard.cprogramming.com/misc....&action=bbcode

    Use the "vB Code" tags to format your future posts.

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    You were close, but you had two major mistakes that was causing it to screw up.

    First off, checked gets set to true only at the beginning of the function, when instead it needs to be set to true before every time you look for duplicates.

    Second, I'm not sure why you set a[n-1]=n. Wouldn't this make it so a[4] always equals 5, and a[3] always equals 4 etc? I think you meant to have that within the for loop and making it so a[n-1]=i. So your new code would look something like this and should work (although I haven't tested it!):
    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void permutations(int m,int n) {
        
        static vector<int> a(n);
        static int N=n;
        bool check=true;
        for(int i=1;i<=m;i++)
            a[n-1]=i;
            if(n==1) {
                checked=true;
                for(int j=0;j<N-1;j++)
                    for(int k=j+1;k<N;k++)
                        if(a[j]==a[k]) check=false;
                if(check) {
                    cout<<'(';
                    for(int j=0;j<N;j++)
                        cout<<a[j]<<',';
                    cout<<')'<<endl;
                }
            }
            else permutations(m,n-1);
    }
    
    int main()
    {
    
    permutations(5,3);
    
     cin.get();
    
    }

  9. #9
    Registered User
    Join Date
    Apr 2003
    Posts
    27
    I tested it and it doesn't print anything.

  10. #10
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,802
    You can use the next_permutation function defined in <algorithm> perhaps. Unless I made a typo:
    Code:
    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    void do_permut(int i1, int i2)
    {
        vector<int> vec;
        int skip = 0;
    
        // Exit if i2 > i1.
    
        if( i2 > i1 ) return;
    
        // Initialize vector.
    
        for( int i = 1; i < i1; ++i ) vec.push_back(i);
    
        // Output the permutations.
    
        do
        {
            if( skip++ % i2 == 0 )
            {
                cout << '(';
                for( int j = 0; j < i2; ++j )
                {
                    cout << vec[j];
                    if( j < (i2-1) ) cout << ',';
                }
                cout << ')' << endl;
            }
        } while( next_permutation(vec.begin(),vec.end()) );
    
    }
    
    int main()
    {
        do_permut(4,2);
        return 0;
    }
    [edit]Tried it with do_permut(4,3) and it didn't work as expected, it does work with (4,2) but the algorithm needs a bit more work I guess. [/edit]
    Last edited by hk_mp5kpdw; 04-28-2003 at 05:11 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  11. #11
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Code:
    #include <iostream>
    #include <assert.h>
    
    using namespace std;
    
    #define MAX_SIZE 50
    
    int cp[ MAX_SIZE ] = { 0 };
    
    void permutations( int m, int n ) {
    
    	int i;
    	int l0 = -1;
    	for( i = 0; i < n; i++ ) {
    		l0 = cp[i] == 0 ? i : l0;
    		if( l0 == i ) break;
    	}
    	if( l0 == -1 ) {
    		for( i = 0; i < n; i++ )
    			cout<<( i == 0 ? '(' : ',' )<<cp[i]<<( i == n - 1 ? ")\n" : " \b" );
    		return;
    	}
    	int fnnu = 1;
    	while( fnnu <= m ) {
    		for( i = 0; i < l0; i++ )
    			if( cp[i] == fnnu ) { fnnu++; goto eol; }
    		cp[l0] = fnnu;
    		permutations( m, n );
    		fnnu++;
    		eol:;
    	}
    	cp[l0] = 0;
    
    }
    
    int main( void ) {
    
    	int m, n;
    	cout<<"m: ";
    	cin>>m;
    	cout<<"n: ";
    	cin>>n;
    	assert( m >= n );
    	permutations( m, n );
    
    	return 0;
    
    }
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  12. #12
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I tested it and it doesn't print anything.
    Oops, didn't notice that you didn't put brackets around your for statement. Enclose the entire for statement in brackets and it should work.

  13. #13
    Registered User
    Join Date
    Apr 2003
    Posts
    27
    Thank you all for your help.One last thing.Are there any non-recursive suggestions-ideas in how this could be done,but without the use of next_permutation in <algorithm>?
    Last edited by k_w_s_t_a_s; 04-27-2003 at 10:59 AM.

  14. #14
    Registered User
    Join Date
    Apr 2003
    Posts
    27
    I am sorry I insist but isn't there anybody who can give some advice for a non-recursive solution?

Popular pages Recent additions subscribe to a feed

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