如何生成带有重复字符的排列

Question

如何生成带有重复字符的排列

3

我想创建由三个操作符组成的字符串（例如：+-*或++/或+++），并将每个字符串推入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...

我该如何实现这个目标？

- turnt

1

你尝试过只使用一堆嵌套的 for 循环吗？ - wlyles

这里有一些很酷的技巧 https://dev59.com/MnE95IYBdhLWcg3wp_yn - doctorlove

3个回答

1

最简单的生成排列的方法是集合积。

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

- Khaled.K

1

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

你可以像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个排列来获得相同的字符串，但对我来说，使用循环似乎更简单。

- user2631937

下一个排列函数（next_permutation）对重复元素也适用。 - doctorlove

1

请添加您的工作代码示例，我会撤销负评。 - Brian

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vinod Sharma · 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.