Running Tests on Multiple Permutations

[thatguy413]

Maybe that's not the best title, but it's close. What I'm looking to do is pull a set number of characters from 3 different arrays, and then run permutations on them, and then pull a different set of characters from the arrays and run permutations on those. On and on until every set of characters has been run against all others to hit every possible permutations with the specified number of characters from each array. I do test each permutation before the next one is computed.

So far I can only hit some of that. I can pull a certain number of characters that change, but I can't figure out how to hit every permutation of characters within the array.

My 3 arrays are capital letters, lower case letters, and numbers. So say I want 3 upper, 2 lower, and 1 number. I would want it to pick ABCab0 and run every permutation. Then ABDab0, ABEab0, ... , ABCac0, ABDac0, ... , ABCab1, ... XYZyz9.

Yes, I know this will take a large amount of time to run through all of this.

This is currently what I'm using:

 
  int i,j = 0;
  int nn = 1;
  int ln = 3;
  int un = 2;
 
   string l = "abcdefghijklmnopqrstuvwxyz";
   string u = "ZYXWVUTSRQPONMLKJIHGFEDCBA";
   string n = "0123456789";
 
   do {
     string a = l.substr(i, ln);
     string b = u.substr(i, un);
     string c = n.substr(j, nn);
     
 
     string s = a + b + c;
     sort(s.begin(), s.end());
 
   do {
         //permutation test
       }
   } while (next_permutation(s.begin(), s.end()));
  
   j++;
   i++; //stops it after success with an error
   if (j == 6)
     j = 0;
   }
while ( i <= (26-un));
 

Edit: I'm not very good at coding, I understand it enough to piece together other codes and make them work for what I need. This piece is mostly my own and that is why it is probably not efficient/has n00b mistakes.

[dutch]

Here's some code that does the combinations part. I left out the permutations but that's easy to add.

In the test data below, the end chars of 'F', 'f', and '2', limit the total combinations generated to 900. If they are changed to 'Z', 'z', and '9', as in your example, the number of combinations is almost 8.5 million. If the permutations were added, permuting those combos (6!=720 perms each) yields about 6 billion total strings.

#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>
using namespace std;

struct ComboData
{
    char   startch; // Using chars from startch ...
    char   endch;   // ... to endch (startch <= endch)
    int    len;     // generate combos of len length
                    // (len <= number of chars in [startch,endch])
    string start;   // Initial string. E.g., 'a','k',3 => "abc"
    string str;     // The string that goes through the combos.

    ComboData(char s, char e, int len) : startch{s}, endch{e}, len{len}
    {
        if (endch < startch || len > endch - startch + 1)
            throw invalid_argument("ComboData::ctor");
        for (int i{}; i < len; ++i) start.push_back(s++);
        str = start;
    }
};

string combine(const vector<ComboData>& cd)
{
    string s;
    for (auto d: cd) s += d.str;
    return s;
}

bool next_combo(string& s, char endch)
{
    size_t i {s.size()};
    while (i > 0)
        if (++s[--i] <= endch--)
        {
            while (i++ < s.size())
                s[i] = s[i - 1] + 1;
            return true;
        }
    return false;
}

int main()
{
    vector<ComboData> cd
    {
        { 'A', 'F', 3 },
        { 'a', 'f', 2 },
        { '0', '2', 1 }
    };

    size_t i {}, cnt {};
    do
    {
        string s {combine(cd)};
        cout << s << '\n';
        ++cnt;

        i = 0;
        for ( ; i < cd.size(); ++i)
        {
            if (next_combo(cd[i].str, cd[i].endch))
                break;
            cd[i].str = cd[i].start;
        }
    }
    while (i < cd.size());

    cout << "cnt: " << cnt << '\n';
}

[lastchance]

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;


bool nextIndices( vector<int> &V, int N )        // V contains current indices; e.g. 0, 1, 2
{                                                // Function tries to advance this to next valid indices (e.g. 0, 1, 3), no repeats
   int last = V.size() - 1;
   V[last]++;                                    // Add 1 to last index
   while( true )
   {
      int i = last;
      while ( V[i] >= N )                        // If final index goes out of range ... increase previous one
      {
         V[i] = 0;
         i--;
         if ( i < 0 ) return false;              // No more choices
         V[i]++;
      }
      if ( set<int>( V.begin(), V.end() ).size() == V.size() ) return true;         // Check no repeats
      V[last]++;
   }
}


int main()
{
   string A = "ABCDE";                           // These are SHORTENED alphabets ... increase as required
   string a = "abcde";
   string x = "01234";
   int numA = 3, numa = 2, numx = 1;             // Number of letters from each alphabet

   vector<int> indicesA( numA, 0 );   indicesA.back() = -1;
   for ( ; nextIndices( indicesA, A.size() ); )
   {
      string AA;
      for ( int i = 0; i < numA; i++ ) AA += A[indicesA[i]];

      vector<int> indicesa( numa, 0 );   indicesa.back() = -1;
      for ( ; nextIndices( indicesa, a.size() ); )
      {
         string aa;
         for ( int i = 0; i < numa; i++ ) aa += a[indicesa[i]];

         vector<int> indicesx( numx, 0 );   indicesx.back() = -1;
         for ( ; nextIndices( indicesx, x.size() ); )
         {
            string xx;
            for ( int i = 0; i < numx; i++ ) xx += x[indicesx[i]];
      
            cout << AA + aa + xx << '\n';
         }
      }
   }
}

ABCab0
ABCab1
ABCab2
ABCab3
ABCab4
ABCac0

... many many lines

EDCec3
EDCec4
EDCed0
EDCed1
EDCed2
EDCed3
EDCed4

For these shortened alphabets (each a choice of 5) you will get 6000 strings.

For full alphabets I think you are looking at
26 x 25 x 24 x 26 x 25 x 10 = 101,400,000 strings
(if you are allowing no repeats).

That's just over 100 million.

[thatguy413]

Ok, Thanks for the help. I will look over those and test them out to see if I have any problems getting them to work.