Thread: Permutation (Perplexed)

  1. #1
    Unregistered
    Guest

    Question Permutation (Perplexed)

    Hi all,

    Can someone please explain why the following short code works in a forward way, but not in reverse order?
    For example: if 1234 is entered, the program generates and prints out correct number permutations, but if 4321 is entered it only prints one permutation, as 4321, why??
    The same goes for abcd - dcba.
    Thanks for any help and enlightenment. Compiler Dev-C++

    //permutation
    #include <iostream>
    #include <algorithm>
    #include <stdlib.h>

    using namespace std;

    int main()
    {
    char v[] = {0};
    cout << "Enter a string: ";
    cin >> v;
    unsigned slen, len = strlen(v);
    unsigned c = 1;

    for(slen = 1; slen <= len; slen++)
    {
    c *= slen;
    }
    cout << v << '\t';
    while(next_permutation(v, v+len))
    {
    cout << v << '\t';
    }
    cout << endl << "\nTotal of perms = " << c << endl << endl;

    system("PAUSE");
    return 0;
    }

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    101
    When you want the permutations in reverse order use prev_permutation instead of next_permutation.
    - lmov

  3. #3
    Registered User
    Join Date
    Dec 2001
    Posts
    194
    Your lucky that code works at all

    snip-----------
    char v[] = {0};
    cout << "Enter a string: ";
    cin >> v;
    unsigned slen, len = strlen(v);
    unsigned c = 1;
    -------------------

    you make the string 1 byte long. When the user enters text it is goin to overflow that buffer, suprising it hasent crashed yet.
    What is an unsigned?
    i think you mean unsigned int

  4. #4
    Unregistered
    Guest
    Salem:
    The next_permutation code is in with algorithm header which comes with Dev-4C++. The code I posted above compiled and worked, but only if the input in a consective number or consective alpha, like abcdef or 12345. When input is mixed, like asdfg and 7459 it does not work properly. Any idea any body I am absolutely baffled! - Thanks for answering.

  5. #5
    Registered User
    Join Date
    Dec 2001
    Posts
    194
    Code:
    	string input;
    	cout << "Enter data:";
    	cin >> input;
    	while( next_permutation(input.begin() , input.end() ) )
    	{
    		cout << input << endl;
    	}
    	return 0;
    I used this code and it worked perfectly has expected.
    If you enter a 3 digit number there are 6 total possible permutations.
    If you enter a 4 digit number there are 24 total possible permutations. The next_permutation function computes the next possible permutation in order.
    If you enter 123 you get
    132
    213
    231
    312
    321
    as output
    But if you enter 213 you only get
    231
    312
    321
    as output, becuase those are the only permutations that come after 213.

    You can mix numbers and letters, but it uses the ascii value.
    If you want to find ALL permutations of a given input, you must make a copy of the input, have one loop start at input and use prev_permutation and have another loop use next permutation.
    If this doesn't clear things up, post the code you are having problems with. The first code you posted had some bugs, which i mentoned before.

  6. #6
    Unregistered
    Guest

    Question

    RpiMatty:
    Thanks for your comment and example of the program. Yeah, I was expecting the program to generate permutation for any given input from scratch. Do you think you could supply me with onather example of your suggestion of using two loops, prev_permutation and next_permutation? or will it easier to rewrite the code from scratch, hence reinventing the wheel?
    Oh come on any other expert coders, please give some help?
    Many thanks in anticipation.

  7. #7
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    Like this -

    Code:
    	string input, input1;
    	cout << "Enter data:";
    	cin >> input;
    	input1=input;
    
    		
    	while( prev_permutation(input.begin() , input.end() ) )
    	{
    		cout << input << endl;
    	}
    	
    	while(next_permutation(input1.begin(), input1.end() ) )
    	{
    		cout << input1 << endl;
    	}
    You'll may want to check for duplicate characters.
    zen

  8. #8
    Unregistered
    Guest

    Question

    zen:
    What are the include header files to use for string, begin(); and end(); - I compiled your code, but the Dev4-C++ threw up a lot of complaints. Here your code I tried to compiled. Thanks for your help.

    #include <iostream>
    #include <stdlib.h>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    int main()
    {
    string input, input1;
    cout << "Enter data:";
    cin >> input;
    input1=input;
    while( prev_permutation(input.begin() , input.end() ) )
    {
    cout << input << endl;
    }
    while(next_permutation(input1.begin(), input1.end() ) )
    {
    cout << input1 << endl << endl;
    }
    system("PAUSE");
    return 0;
    }

  9. #9
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    #include <string>
    zen

  10. #10
    Unregistered
    Guest

    Wink

    Many thanks zen, and happy New Year to all who helped. Program works properly now. One more question, can I use this permutation to solve, say what is an anagram of supersonic? - an answer is repercussion. It seems I need to store input and input1 into an array before I can compare an answer to the input question? Any suggestions, bright ideas? - Thanks.

  11. #11
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    repercussion is an anagram of supersonic....... lol

    are you sure......

    you can use next_permutation and prev_permutation to do what you want as zen has shown you but it will never turn supersonic into repercussion. lol
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  12. #12
    Unregistered
    Guest

    Unhappy

    Stoned_Coder:

    Sorry, I meant turn supersonic to percussion in anagram. Will post the code sometime later...Thanks for pointing it out.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bit level permutation function
    By zxcv in forum C Programming
    Replies: 2
    Last Post: 07-27-2008, 01:26 PM
  2. Problem creating a recursive string permutation function
    By indigo0086 in forum C++ Programming
    Replies: 4
    Last Post: 10-10-2006, 10:09 AM
  3. Permutation algorithm??
    By lris2005 in forum C++ Programming
    Replies: 1
    Last Post: 04-01-2006, 06:51 AM
  4. Permutation Calculation
    By Eric Hansen in forum C++ Programming
    Replies: 21
    Last Post: 06-11-2003, 04:03 PM
  5. INT ARRAY Permutation!
    By arthur5005 in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2002, 05:30 AM