Permutations of String

[QK11nhu]

I'm attempting to find the most efficient method of returning the inverse permutation for a rearranged string, such that each character assumes the position it would have held in the original string, but instead replaced with the new character.

For example;

S1 -------------------------------- ABCDEFGHIJKLMNOPQRSTUVWXYZ.,'_
S1 PERMUTATION --------------- MBJYA,ZV_PS'ONXQ.DURITWKCHGLFE
S1 INVERSE PERMUTATION ---- EBYR_'.ZUCX,ANMJPTKVSHWODGQFLI

The character 'M' takes the position of 'A', in the permutation.
Thus character 'A' takes the original position of 'M' in the inverse permutation.

Similarly character 'J' takes the position of 'C', in the permutation.
So for the inverse permutation the character 'C' is moved to the position originally occupied by 'J'.

Would anyone be able to offer some advise on how to translate this into code?

Below is the function being used to generate the first permutation, if that may help. Thanks in advance for any assistance offered.

#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ.,' ";

string create_permutation(unsigned seed) 
{
	srand(seed);
	string permutation = ALPHABET;  // using built-in random generator //
	random_shuffle(permutation.begin(), permutation.end());
	return permutation;
}

int seed = 1; // seed for generating permutation //
string permu1 = create_permutation(seed);

int main()
{
	cout << "Permutation of ALPHABET: " << permu1 << endl;
	
	cout << "Inverse permutation: " << /* [inverse goes here] <<*/  endl;
	
	return 0;
}

[D80DSL3A]

I have some ideas. The mapping seems straightforward enough.
Let permStr be the given permutation of ALPHABET and invPermStr is to contain the inverse permutation.
Assuming that invPermStr is already sized so we can make assignments to its elements, then we want:

// all strings are the same size
for( size_t i = 0; i<ALPHABET.length(); ++i )
        for( size_t j = 0; j<ALPHABET.length(); ++j )// O(n2) mapping        
            if( permStr[i] == ALPHABET[j] )
            {
                invPermStr[j] = ALPHABET[i];
                break;
            }        

Now, if ALPHABET didn't have those last 4 odd characters, this could be done more directly.

const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

for( size_t i = 0; i<ALPHABET.length(); ++i )// O(n) mapping
    invPermStr[ permStr[i]-'A' ] = ALPHABET[i];

I have gotten a hybrid approach working though:

for( size_t i = 0; i<ALPHABET.length(); ++i )
{
    if( permStr[i] >= 'A' && permStr[i] <= 'Z' )// index direct
        invPermStr[ permStr[i]-'A' ] = ALPHABET[i];
    else// search for it        
        for( size_t j = 26; j<ALPHABET.length(); ++j )            
            if( permStr[i] == ALPHABET[j] )
            {
                invPermStr[j] = ALPHABET[i];
                break;
            }
}

I'll share my code for the simpler case.

#include <iostream>
#include <string>
#include <array>
#include<algorithm>
#include <random>       // std::default_random_engine
#include <chrono>       // std::chrono::system_clock

using std::cout;

const std::string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

std::string create_permutation( std::string permutation )
{
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle( permutation.begin(), permutation.end(), std::default_random_engine(seed) );
return permutation;
}


// courtesy JLBorges from: http://www.cplusplus.com/forum/beginner/189063/#msg916749
// this will work with the longer ALPHABET also
bool is_permutation( const std::string& a, const std::string& b  )
{
    if( a.size() != b.size() ) return false ;

    static constexpr std::size_t N = std::numeric_limits<unsigned char>::max() + 1 ;

    std::array<std::size_t,N> aa {} ;
    for( unsigned char c : a ) ++aa[c] ;

    std::array<std::size_t,N> bb {} ;
    for( unsigned char c : b ) ++bb[c] ;

    return aa == bb ;
}

std::string findInversePerm( const std::string& permStr )
{
    if( !is_permutation(permStr, ALPHABET) ) return std::string();// empty string

    std::string invPermStr(ALPHABET);// actually, just need the sizes =
    for( size_t i = 0; i<permStr.length(); ++i )
        invPermStr[ permStr[i]-'A' ] = ALPHABET[i];

    return invPermStr;
}


int main()
{
    std::string perm = create_permutation(ALPHABET);
    bool isPerm = is_permutation(perm, ALPHABET);
    cout << "perm " << ( isPerm ? "is" : "isn\'t" ) << " a permutation of ALPHABET\n";

    if( isPerm )
    {
        std::string invPerm = findInversePerm( perm );
        cout << "\nALPHABET =  " << ALPHABET << '\n';
        cout << "perm     =  " << perm << '\n';
        cout << "invPerm  =  " << invPerm << '\n';
        cout << "perm back?  " << findInversePerm( invPerm ) << '\n';
    }

    return 0;
}

Notice that perm = findInversePerm( findInversePerm( perm ) );

[QK11nhu]

Funnily, the suggestions you've made look very familiar to my solution to a previous part of the problem, which involved verifying which characters belonged to the string, and their position. The last four characters are indeed problematic - in the previous part I used a switch statement to simply replace those characters with the number of their position in the string, however in this situation, the permutation means that those characters can be at any position, dependent on how the permutation is seeded. I'll see if I can get the hybrid approach to work with what I've been working on though. Thanks again.

[D80DSL3A]

Cool. Glad it's useful.
All 3 codes at the top of my last post work.
The 1st code will work on an alphabet with any mix of unique characters.
The 3rd code will work only with an ALPHABET = "ABC...XYZ + "<$/]#{";
Code frag #2 is currently in findInversePerm(), but substitute one of the other frags, and it should work on the longer ALPHABET.

[QK11nhu]

Had a brief moment of despair when it announced that there was a 'debug assertion failure' after attempting to run what I had, but I've now realised what I'd done wrong and have it working with the longer alphabet. Thanks very much!

[D80DSL3A]

Did you finish? I continued work to explore how different alphabet types affect algorithmic efficiency.
I consider 3 alphabet types, all of which have no repeated values. All are a set of unique elements.

type 1. Elements are ordered by value and all values are sequential.
value lookup = O(1). Calculate position.
eg: ABCDEFGHIJKLMN

type 2: Elements are ordered by value these are not sequential. Values are skipped.
value lookup = O(logn). Binary search may be used.
eg. AEIJMNOQRTUVXZ

type 3: Elements are unordered.
value lookup = O(n). value could be anywhere. Sequential search good as any.
eg. XETIAVQJMORNUZ

Note that a type 3 is any permutation of a type 1 or 2.
There is only one permutation in which all elements are ordered.
A type 3 can be sorted to obtain a type 2, or possibly a type 1 (the unique ordered permutation).

The code below will generate a permutation of the selected alphabet type, find the inverse permutation, then inverse permute that to verify we get the original permutation back.
The user is prompted to choose an alphabet type.

The findInversePerm() function handles all 3 cases by farming out the inner iteration to a findEle() function.
This function employs the appropriate method to lookup an element index in alpha: direct calculation if alpha is type 1, binary search if type 2, or a sequential search if type 3.
The binary search code is adapted from something I wrote long ago. I found it in a folder of old codes of mine copied from an old computer.

This should run in the shell here. I organized the code as best I could, but there's a bit of it.
I think I have a fairly comprehensive treatment pulled together nicely here.
Hope you find it interesting:

// inverse permutation mapping problem
#include <iostream>
#include <string>
#include <array>
#include<algorithm>
#include <random>
#include <chrono>

using std::cout;
using std::string;

// the core functions
string create_permutation( string alpha );// generate permutation of given string
bool is_permutation( const string& a, const string& b  );// courtesy JLBorges. Works for general alphabet
string findInversePerm( const string& permStr, const string& alpha );// Generic. Uses findEle(), which deals with the alpha classification

// utility and helper functions
int classifyALPHABET( const string& alpha );// returns: 1 = O(1), 2 = O(logn), 3 = O(n) lookups
int findEle( char c, const string& alpha_ord, int alphaType );// employs method appropriate to the alphaType. returns -1 by default
int bin_search( char c, const string& alpha_ord );// returns index where c appears in alpha_ord for alpha_ord only. -1 if not found
int bs_rec( const char val, const char* pa, int lo, int hi );// recursive helper callled by bin_search()


int main()//**************** MAIN ************************
{
// The 3 alphabet types
    const string ALPHA_SeqOrd = "ABCDEFGHIJKLMN";// ordered sequential values = O(1) value lookup
    const string ALPHA_Ord    = "AEIJMNOQRTUVXZ";// ordered but non-sequential values = (logn) lookup
    const string ALPHA_Rand   = "XETIAVQJMORNUZ";// random order. Worst case = O(n) lookup

    int choice = 0;
    cout << "Choose an alphabet type\n";
    cout << "1: Element values ordered and sequential. O(1) lookup.\n";
    cout << "2: Element values ordered, but not sequential. O(logn) lookup.\n";
    cout << "3: Values in random order = permutation of type 2 above. O(n) lookup.\n";
    cout << "type: ";
    std::cin >> choice;

    const string* pAlpha = nullptr;
    switch( choice )
    {
        case 1: pAlpha = &ALPHA_SeqOrd; break;
        case 2: pAlpha = &ALPHA_Ord; break;
        case 3: pAlpha = &ALPHA_Rand; break;
        default: return 1;
    }

    if( !pAlpha ) return 2;
    const string& rAlpha = *pAlpha;// for notational convenience in following code

    std::string perm = create_permutation(rAlpha);// generate permutation of selected alphabet type
    bool isPerm = is_permutation(perm, rAlpha);// verify that perm is a permutation of rAlpha
    if( isPerm )
    {
        std::string invPerm = findInversePerm( perm, rAlpha );// generate the inverse permutation

        cout << "\nalpha    =  " << rAlpha << " type: " << classifyALPHABET( rAlpha ) << '\n';// show alpha and type
        cout << "perm     =  " << perm << '\n';
        cout << "invPerm  =  " << invPerm << '\n';
        cout << "perm back?  " << findInversePerm( invPerm, rAlpha ) << '\n';// inv inv permute
    }
    else
        cout << "perm isn\'t a permutation of " << rAlpha << '\n';

    return 0;
}// end of main()

std::string create_permutation( std::string alpha )
{
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle( alpha.begin(), alpha.end(), std::default_random_engine(seed) );
return alpha;
}

// courtesy JLBorges
bool is_permutation( const std::string& a, const std::string& b  )
{
    if( a.size() != b.size() ) return false ;

    static constexpr std::size_t N = std::numeric_limits<unsigned char>::max() + 1 ;

    std::array<std::size_t,N> aa {} ;
    for( unsigned char c : a ) ++aa[c] ;

    std::array<std::size_t,N> bb {} ;
    for( unsigned char c : b ) ++bb[c] ;

    return aa == bb ;
}

int classifyALPHABET( const string& alpha )// returns: 1 = O(1), 2 = O(logn), 3 = O(n) lookups
{
    if( alpha.length() < 2 ) return 1;

    int classification = 1;// best case assumed
    int currVal = 0, lastVal = (int)alpha[0];

    for( size_t i = 1; i < alpha.length(); ++i )
    {
        currVal = (int)alpha[i];
        if( currVal < lastVal ) return 3;// random order. Must be checked for to end of alpha
        if( currVal != lastVal + 1 )
            classification = 2;// can't break. Above condition may still be found.
        lastVal = currVal;
    }

    return classification;
}

// employs method appropriate to the alphabet type. alphaType must be correct.
// This method would be private in a class. Returns index to element where c found.
int findEle( char c, const string& alpha_ord, int alphaType )
{
    switch( alphaType )
    {
    case 1:// O(1) lookup = calculate result
        return (int)( c - alpha_ord[0] );
    case 2:// O(logn) lookup = at least they're in order
        return bin_search( c, alpha_ord );
    case 3:// O(n) lookup = could be anywhere. Sequential search good as any.
        for( size_t i=0; i < alpha_ord.length(); ++i )
            if( c == alpha_ord[i] ) return i;
    }

    // this handles default case
    return -1;// dangerous return value?
}

// precond: alpha_ord is correct type = ordered perm
int bin_search( char c, const string& alpha_ord )// returns index where c appears in alpha_ord
{
    int idx = bs_rec( c, alpha_ord.c_str(), 0, (int)alpha_ord.length() - 1 );
    if( alpha_ord[idx] == c ) return idx;
    return -1;// fail
}

int bs_rec( const char val, const char* pa, int lo, int hi )
{
    if( lo < hi )
    {
        int mid = (lo+hi)/2;
        if( val == pa[mid] ) return mid;// new
        if( val < pa[mid] ) return bs_rec( val, pa, lo, mid );// new
//        if( val <= pa[mid] ) return bs_rec( val, pa, lo, mid );// old
        return bs_rec( val, pa, mid+1, hi );
    }
    return lo;
}

// generic. findEle() fields cases.
std::string findInversePerm( const std::string& permStr, const string& alpha )
{
    if( !is_permutation( permStr, alpha ) ) return std::string();// empty string
    int alphaClass = classifyALPHABET( alpha );
    if( alphaClass == -1 ) return std::string();// empty string

    std::string invPermStr( alpha );// actually, just need the sizes =
    for( size_t i = 0; i < alpha.length(); ++i )
    {
        int j = findEle( permStr[i], alpha, alphaClass );
        if( j >= 0 ) invPermStr[j] = alpha[i];
    }

    return invPermStr;
}

edit: improvement in bs_rec() code.

[QK11nhu]

I did successfully finish that task, yes. I won't pretend to understand all of what's going on in the above functions as I'm relatively new to C++, but it was definitely very interesting to look through. Which type would the alphabet used for the task I was given be classed as in this case? I would assume type 3, as the elements are initially ordered with sequential value ("ABCD", etc), however then have unordered, non-sequential characters at the end of the string (".,' ") which would need to be reordered into type 2.

[D80DSL3A]

I'm glad you liked that.
That's exactly right about the alphabet type.
We were almost given a type 1 alphabet, but 4 random trailing chars turned it into a type 3. Sorting it would give us a type 2 alphabet, then binary search could be applied during the inverse permutation operation.