Как создавать перестановки с повторяющимися символами

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... 

Как я могу добиться этого?

Answer 1

Использование рекурсии для печати того, что вы просили. Адаптация его для хранения строки перестановки в векторах должна быть тривиальной. Я не программист на 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. 

Answer 2

Строки с повторяющимися элементами не могут быть перестановками, потому что перестановка - это упорядочение.

Вы можете сделать это с помощью 3 вложенных циклов, как сказал wlyles.

Edited добавить:

Это будет печатать строки, я думаю, вы хотите. Вы можете заменить инструкцию 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-перестановки набора {"+","+","+","-","-","-","*","*","*","/","/","/"}, но использование циклов мне кажется более простым.

Answer 3

Самый простой способ генерации перестановок устанавливается продукт ..

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