1

我是 C++ 新手，我正在开发一个程序，该程序将生成一个字符串的所有排列的列表，但是我需要能够将输出的长度限制为 5 个字符（这很可能会变成用户设置的变量号）。我一直在寻找大约一周的时间来寻找这样的东西，而我得到的最接近的是以下代码。

源.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();
}

此代码有效，但它不限制输出的长度。它将输出长度设置为给定字符串的长度。看起来它可能不会在输出中解释多个相同的字母/数字（这我不是 100% 确定）。

此外，我需要设置特殊规则，例如连字符不能是输出中的第一个或最后一个字符。

我试图通过将sizeof(str)-1替换为5来修改上述代码，但是它只会“循环”字符串中的前 5 个字符，因此不会处理“e”之外的任何内容。

如果有人可以在这方面提供帮助，将不胜感激。

编辑：

感谢大家的出色帮助，我现在将发布我的最终产品，以防其他人尝试做同样的事情。

最终来源：

#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;
}
4

2 回答 2

1

您需要限制递归的深度

要给出字符串中字符的排列，每个只使用一次： 

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]);
    }
  }
}

像这样打电话

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

要给出字符串中字符的排列，请无限次使用每个字符：

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);
    }
  }
}

像这样打电话

  char result[5];
  permutation(str, sizeof(str)-1, result, 0, sizeof(result));
于 2013-04-17T10:05:33.340 回答
0

这实际上并不是一项艰巨的工作。如果您可以在该函数中使用递归和循环，则可以解决它。我建议使用next_permutation标准库中的函数。

事实就是时间。在 3 秒内，您只能处理 8 个字符的排列。并且条件将取决于要求。假设在您的示例中，如果您需要在开始或结束时省略连字符，您可以修剪回来。

我的实现的伪代码：

    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);
          }
       }
    }

最初调用此函数recur(0, 5)

于 2013-04-17T09:20:23.580 回答