c++ - 如何使用重复字符生成排列

Question

我基本上想创建由三个操作符号（例如：+-*或++/或+++）组成的字符串。这些字符串中的每一个都应该被推入vector <string> opPermutations 这是我到目前为止的代码：

 // Set up permutations for operators

string operatorBank[4] = {"+","-","*","/"};

 do {

    string currentPerm = operatorBank[0] + operatorBank[1] + operatorBank[2] + operatorBank[3];

    this -> opPermutations.push_back(currentPerm);

} while ( std::next_permutation(operatorBank, operatorBank + 4) );

推入向量（作为字符串）的排列是：

然而，我想要的是让我的排列像这样存在：

每个应该是三个字符的长度
每一种可能的排列，包括一个字符重复多次的排列，都必须存在。

我希望它这样组织：

+++
---
*** 
/// 
/*/
+-+
++*
**/

etc...

我怎样才能做到这一点？

score 2 · Accepted Answer

使用递归打印您所要求的内容。调整它以将排列字符串存储在向量中应该是微不足道的。我不是 C++ 程序员，所以在 C++ 中可能有更好的方法。但这里的主要思想是使用递归。

    #include <iostream>
    #include <string>
    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;

    void displayPermutation(string permutation[], int length){
        int i;
        for (i=0;i<length;i++){
            cout<<permutation[i];
        }
        cout << endl;
    }

    void getPermutations(string operatorBank[], int operatorCount, 
            string permutation[],int permutationLength, int curIndex){
        int i;
        //stop recursion condition
        if(curIndex == permutationLength){
            displayPermutation(permutation,permutationLength);
        }
        else{
            for(i = 0; i < operatorCount; i++){
                permutation[curIndex] = operatorBank[i];
                getPermutations(operatorBank,operatorCount,permutation,
                    permutationLength,curIndex+1);
            }
        }
    }

    int main ()
   {
       int operatorCount = 4;
       int permutationLength = 3;
       string operatorBank[] = {"+","-","*","/"};
       string permutation[] = {"","","",""}; //empty string
       int curIndex = 0;
       getPermutations(operatorBank,operatorCount,permutation,
                                   permutationLength,curIndex);
       return 0;
   }

输出：

   +++
   ++-
   ++*
   ++/
   +-+
   +--
   +-*
   +-/
   +*+
   +*-
   +**
   +*/
   +/+
   +/-
   +/*
   +//
   .
   .
  and so on.

score 1 · Accepted Answer

生成排列的最简单方法是 Set Product ..

list<string> setProduct (list<string> a, list<string> b)
{
    list<string> L;
    list<string>::iterator i, j;

    for(i = a.begin(); i != a.end(); ++i)
        for(j = b.begin(); j != b.end(); ++j)
            L.push_front(*i + *j);

    return L;
}

list<string> permute (list<string> a, int len)
{
     list<string> L;

     while (len --> 0) L.splice(a.end(), setProduct(L,a));

     return L;
}

score 1 · Accepted Answer

具有重复元素的字符串不是可能的排列，因为排列是一种排序。

正如 wlyles 所说，您可以使用 3 个嵌套的 for 循环来做到这一点。

编辑添加：

这将打印我认为你想要的字符串。您可以将 cout 语句替换opPermutations.push_back(operatorBank[i]+operatorBank[j]+operatorBank[k])为添加到向量中。

#include <iostream>
#include <string>

int main(){
  std::string operatorBank[4] = {"+","-","*","/"};

  for (int i=0; i<4; ++i){
    for (int j=0; j<4; ++j){
      for (int k=0; k<4; ++k){
        std::cout << operatorBank[i] << operatorBank[j] << operatorBank[k] << std::endl;
      }
    }
  }

  return 0;
}

我认为混淆可能在于“排列”一词。您可以获得与集合的 3 排列相同的字符串，{"+","+","+","-","-","-","*","*","*","/","/","/"}但使用循环对我来说似乎更简单。

c++ - 如何使用重复字符生成排列

3 回答 3

Related

Reference