How to Generate Permutations With Repeated Characters

Question

I basically want to create strings that consist of three operation symbols (eg: +-* or ++/ or +++). Each one of these strings should be pushed into vector <string> opPermutations This is my code so far:

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

The permutations that are pushed into the vector (as strings) are:

What I want however is to have my permutations exist like this:

Each should be three characters in length
Every possible permutation, including the ones in which a character is repeated more than one time, must be present.

I want it to be organized as such:

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

etc...

How can I achieve this?

There are some cool tricks here http://stackoverflow.com/questions/2211915/combination-and-permutation-in-c/ — doctorlove, Jul 29 '13 at 22:06

score 2 · Accepted Answer · answered Jul 29 '13 at 22:58

Using the recursion to print what you asked. Adapting it to store permutation string in vectors should be trivial. I am not a c++ programmer,so there may be better way to do it in C++. but the main idea here is to use recursion.

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

output:

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

Not very practical, but still an awesome solution! – Kirill Starostin May 02 '18 at 06:28 — Kirill Starostin, May 02 '18 at 06:28

user2631937 · Answer 2 · 2013-07-29T22:55:23.173

Strings with repeated elements are not possible permutations, because a permutation is an ordering.

You can do this with 3 nested for loops as wlyles said.

Edited to add:

This will print the strings I think you want. You can replace the cout statement with opPermutations.push_back(operatorBank[i]+operatorBank[j]+operatorBank[k]) to add to the vector.

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

I think maybe the confusion is over the term "permutation." You could get the same strings as 3-permutations of the set {"+","+","+","-","-","-","*","*","*","/","/","/"} but using loops seems simpler to me.

Please add a code example of your work and I will reverse the down vote. — Brian, Jul 29 '13 at 22:22

score 1 · Answer 3 · answered Jul 30 '13 at 08:51

Easiest way to generate permutations is 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;
}

How to Generate Permutations With Repeated Characters

3 Answers3

Linked