C++ Permutation with a output length limit and special arguments

Question

I am new to C++ and I am working on a program that will generate a list of all permutations of a string of characters, however I need the ability to limit the length of the output to lets say 5 characters (this will most likely become a variable number set by the user). I have been searching for about a week for something like this and the closest I have gotten is the following code.

Source.cpp:

#include <iostream>;

using namespace std;

void swap(char *fir, char *sec)
{
  char temp = *fir;
  *fir = *sec;
  *sec = temp;
}

/* arr is the string, curr is the current index to start permutation from and size is sizeof the arr */
void permutation(char * arr, int curr, int size)
{
  if(curr == size-1)
  {
    for(int a=0; a<size; a++)
        cout << arr[a] << "";
    cout << endl;
  }

  else
  {
    for(int i=curr; i<size; i++)
    {
        swap(&arr[curr], &arr[i]);
        permutation(arr, curr+1, size);
        swap(&arr[curr], &arr[i]);
    }
  }
}

int main()
{
  string next;
  char str[] = "abcdefghijklmnopqrstuvwxyz1234567890-";

  permutation(str, 0, sizeof(str)-1);
  cin.get();
  cin.get();
}

This code works however it does not limit the length of the output. It sets the output length to the length of the given string. It also appears it might not account for multiple of the same letter/number in the output (this I am not 100% sure of).

Additionally, I will need to set special rules such as the hypen cannot be the first or last character in the output.

I have attempted to modify the above code by replacing sizeof(str)-1 with 5 however it will only "loop" through the first 5 characters in the string, so anything beyond "e" is not processed.

If anyone can assist on this it would be much appreciated.

EDIT:

Thank you to everyone for their excellent help I am now going to post my final product in case anyone else was trying to do the same thing.

Final Source:

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>

using namespace std;

void swap(char *fir, char *sec)
{
  char temp = *fir;
  *fir = *sec;
  *sec = temp;
}

void permutation(char * arr, int size, char* result, int depth, int limit)
{
  ofstream myfile ("permutation.txt", fstream::app);
  if(depth == limit)
  {
    for(int a=0; a<limit; a++){
      myfile << result[a] << "";
      cout << result[a] << "";
    }
    myfile << "\n";
    cout << endl;
  }
  else
  {
    for(int i=0; i<size; i++)
    {
      result[depth] = arr[i];
      permutation(arr, size, result, depth + 1, limit);
    }
  }
  myfile.close();
}

int main()
{
  ofstream myfile ("permutation.txt");
  myfile << "";
  myfile.close();
  string answer;
  char *rArray;
  string startProcess = "N";
  std::cout << "Welcome to permutation v1" << endl;
  std::cout << "-------------------------" << endl;
  std::cout << "Please enter how long the string should be: ";
  std::getline (std::cin,answer);
  int result = atoi(answer.c_str());
  rArray = new char[result];
  std::cout << "\n\nThank You!\n" << endl;
  std::cout << "Please wait, generating possible character array for length of " << result << "." << endl;
  std::cout << "Would you like to proceed? Y = yes & N = no: ";
  std::getline (std::cin,startProcess);
  char str[] = "abcdefghijklmnopqrstuvwxyz1234567890";
  if(startProcess == "Y")
  {
    permutation(str, sizeof(str)-1, rArray, 0, result); 
  }
  else
  {
    std::cout << "\n\nOperation Terminated. No permutations being generated..." << endl;
  }
  cin.get();
  return EXIT_SUCCESS;
}

There's no need to implement your own `swap` function, as there is one in the [standard library](http://en.cppreference.com/w/cpp/algorithm/swap). — Some programmer dude, Apr 17 '13 at 09:04
As for your question, do you only want to output the first five characters in the string, or the five first permutations? — Some programmer dude, Apr 17 '13 at 09:10
this might be what you want to do http://stackoverflow.com/questions/9217839/finding-all-the-unique-permutations-of-the-string — Angel Koh, Apr 17 '13 at 09:20
Updated to do what you actually wanted without having to enter multiple characters — parkydr, Apr 17 '13 at 19:31

parkydr · Accepted Answer · 2013-04-17T19:49:44.123

You need to limit the depth of the recursion

To give permutations of characters in the string, using each only once:

void permutation(char * arr, int currsize, intchar* sizeresult, int depth, int limit)
{
  if(depth == limit)
  {
    for(int a=0; a<limit; a++)
        cout << arr[a]result[a] << "";
    cout << endl;
  }
  else
  {
    for(int i=curr;i=0; i<size; i++)
    {
        swap(&arr[curr],result[depth] &arr[i]);= arr[i];
        permutation(arr, curr+1size, sizeresult, depth + 1, limit);
        swap(&arr[curr], &arr[i]);
    }
  }
}

Call like this

permutation(str, 0, sizeof(str)-1, result, 0, 5);

To give permutations of characters in the string, using each character an unlimited number of times:

void permutation(char * arr, int size, char* result, int depth, int limit)
{
  if(depth == limit)
  {
    for(int a=0; a<limit; a++)
        cout << result[a] << "";
    cout << endl;
  }
  else
  {
    for(int i=0; i<size; i++)
    {
        result[depth] = arr[i];
        permutation(arr, size, result, depth + 1, limit);
    }
  }
}

Call like this

  char result[5];
  permutation(str, sizeof(str)-1, result, 0, sizeof(result));

thank you this does seem to work somewhat, however what I feared early appears true. This does not allow for a character to appear more than once in the string. for instance: aaaaa, aaaab they would be valid output that i seek as well and the code i have so far will not list those characters more than once in the string — Garrett Innovations, Apr 17 '13 at 19:01
i might have fixed it without modifying the code. this may be unconventional but if i add the possible character 5 times in the initial array it seems to print like it should. If there is a better way of doing this please let me know — Garrett Innovations, Apr 17 '13 at 19:12
thank you very much. It's working like a charm. I will post the working code below in case anyone else needs it. — Garrett Innovations, Apr 18 '13 at 04:26

score 0 · Answer 2 · edited Apr 17 '13 at 09:56

This is not a tough job actually. If you can use recursion and a loop within that function you can solve it. I suggest use next_permutation function from the standard library.

The fact is time. Within 3 second you can process permutation for only 8 character. And the condition will be depended to requirement. Suppose in your example you can prune back if you need to omit hyphen in starting or ending.

Pseudo code of my implementation:

    char array[] = "abcdee";
    char eachPerm[6];
    bool usedmatrix[6][6];
    Recur(int depth, int n)
    {
       // you can return from here if this is not the right path, suppose '-'
       // in first or last place.
       if(depth == n)
       {
          print;
       }
       else
       {
          int i;
          for(i= 0 to array.length)
          {
               if(array[i] is not used before)
               eachPerm[depth] = array[i];
               recur(depth+1, n);
          }
       }
    }

Call this function initially recur(0, 5)

C++ Permutation with a output length limit and special arguments

Source.cpp:

EDIT:

Final Source:

2 Answers2