#include #include #include /* Enable tracing of an iterative combination search algorithm */ //#define TRACE_ITERABLE_PERMUTATION /* Search for a string when viewing a string permutation iterator with a unique permutation cache. Judging by the test results, my algorithm for enumerating permutations differs from the standard one and therefore the total number of permutations converges, but their positions in enumeration are different - I honestly don’t know how to fix it ... maybe, who knows? C++ Solution With using Standart Library https://code.sololearn.com/czhcQ0lQWDG5 Thanks ChillPill - information for the correct solution: http://wordaligned.org/articles/next-permutation Good Solution by HonFu https://code.sololearn.com/cjnQHfjKjZm5/?ref=app based from: https://www.geeksforgeeks.org/johnson-trotter-algorithm/ (It is not implemented in this code. In this code my bicycle....) */ #ifdef TRACE_ITERABLE_PERMUTATION #define _printf_IP printf #else #define _printf_IP if(0)printf #endif void swap(char *x, char *y); int charcmp( const void* a, const void* b); char* cReplSpaces(int n); #define STACK_PERMITERDATA_GROW 10 typedef struct { int l, r, i, bLoop; } PermIterData_t; typedef struct { int iCArraySize; char *cPermCArray; PermIterData_t* pStack; int iStackSize; int iStackMemSize; } PermCArrGen_t; int PermCArrayGen_create( PermCArrGen_t** ppObj, char *a, int n ); char* PermCArrayGen_next( PermCArrGen_t* pObj ); int PermCArrayGen_destroy( PermCArrGen_t** ppObj ); #define GROW_SORTEDARRAY_CMBSTR 8 typedef struct { char *aCmbStrs; int iaCmbStrsMemSize, iaCmbStrsSize, iCmbStrLen; } CmbStrSortArray_t; int CmbStrSortArray_create(CmbStrSortArray_t** ppArr, int n); int CmbStrSortArray_destroy(CmbStrSortArray_t** ppArr); int CmbStrSortArray_add(CmbStrSortArray_t *pCmbStrSortArray, char* cmbstr); void CmbStrSortArray_print( CmbStrSortArray_t* pArr ); //Solution With out using Standart Library - Correct but... int main() { PermCArrGen_t* pPermCArrGen = NULL; CmbStrSortArray_t *pCmbStrSortArray = NULL; //Example string (character array) to demonstrate permutation algorithms char bstr[1000] = {0}, str[1000] ={0}; //fgets( bstr, sizeof(bstr), stdin); strcpy( bstr, "SOLOLEARN" ); strcpy(str, bstr); int n = strlen(str); qsort( str, n, sizeof(char), charcmp ); if( CmbStrSortArray_create( &pCmbStrSortArray, n ) ){ int iIterableCounter = 0, bAddedNew; if(PermCArrayGen_create( &pPermCArrGen, str, n) ){ char *cmbstr = NULL; while( (cmbstr = PermCArrayGen_next( pPermCArrGen) ) ){ bAddedNew = CmbStrSortArray_add( pCmbStrSortArray, cmbstr); if( bAddedNew ){ iIterableCounter++; if( strcmp(cmbstr, bstr) == 0 ){ printf("[%6i] Found Permutation Equal Base Str: \"%s\"\n", iIterableCounter, cmbstr); //break; }; }; }; PermCArrayGen_destroy(&pPermCArrGen); }; printf("Count Permutations %i \n", iIterableCounter ); CmbStrSortArray_destroy( &pCmbStrSortArray ); }; return 0; } void swap(char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } int charcmp( const void* a, const void* b) { return (*(char*)a == *(char*)b) ?0:(*(char*)a < *(char*)b)?-1:1; }; char* cReplSpaces(int n){ static char cBuf[1000]; int nn = (n < sizeof(cBuf))?n:(sizeof(cBuf) - 1); memset(cBuf, ' ', nn); cBuf[nn] = 0; return cBuf; } int PermCArrayGen_create( PermCArrGen_t** ppObj, char *a, int n ){ if(ppObj == NULL)return 0; if(a == NULL)return 0; if(n <= 0)return 0; int iRes = 0; *ppObj = (PermCArrGen_t*)calloc( 1, sizeof(PermCArrGen_t) ); if(*ppObj){ PermCArrGen_t* pObj = *ppObj; iRes = 1; pObj->cPermCArray = (char*)malloc((n+1)); if(pObj->cPermCArray){ memcpy(pObj->cPermCArray, a, n); pObj->cPermCArray[n] = 0; pObj->iCArraySize = n + 1; } else iRes = 0; if(iRes){ pObj->iStackMemSize = STACK_PERMITERDATA_GROW; pObj->iStackSize = 0; pObj->pStack = (PermIterData_t*)calloc( pObj->iStackMemSize, sizeof(PermIterData_t) ); if(!pObj->pStack){ pObj->iStackMemSize = 0; iRes = 0; }; }; if(!iRes){ if(pObj->cPermCArray){ free(pObj->cPermCArray); pObj->cPermCArray = NULL; }; } else { pObj->iStackSize = 1; pObj->pStack->l = 0; pObj->pStack->r = n - 1; pObj->pStack->i = pObj->pStack->l; pObj->pStack->bLoop = 0; _printf_IP("%sPush Stack: { a = \"%s\", l = %i, r = %i } \n", cReplSpaces(pObj->iStackSize), pObj->cPermCArray, pObj->pStack->l, pObj->pStack->r); } }; if(!iRes){ if(*ppObj){ free(*ppObj); *ppObj = NULL; }; }; return iRes; } char* PermCArrayGen_next( PermCArrGen_t* pObj ){ if(pObj == NULL)return NULL; if(pObj->iStackSize == 0)return NULL; char *retstr = NULL; PermIterData_t* pStackPos = ( pObj->pStack + (pObj->iStackSize - 1) ); while(1){ if (pStackPos->l == pStackPos->r) { retstr = pObj->cPermCArray; _printf_IP("%sPopUp Stack \n", cReplSpaces(pObj->iStackSize)); pObj->iStackSize--; if(pObj->iStackSize > 0){ pStackPos--; }; break; } else { int lp, rp; if( !(pStackPos->bLoop) ){ _printf_IP("%sBegin Iteration Loop: { from i = %i while i <= %i } \n", cReplSpaces(pObj->iStackSize), pStackPos->l, pStackPos->r); swap( (pObj->cPermCArray + pStackPos->l), (pObj->cPermCArray + pStackPos->i) ); lp = pStackPos->l + 1; rp = pStackPos->r; pStackPos->bLoop = 1; } else { swap( (pObj->cPermCArray + pStackPos->l), (pObj->cPermCArray + pStackPos->i) ); pStackPos->i++; _printf_IP("%sNext Iteration: { i ++ = %i } { l = %i, r = %i } \n", cReplSpaces(pObj->iStackSize), pStackPos->i, pStackPos->l, pStackPos->r ); if( pStackPos->i > pStackPos->r ){ pStackPos->bLoop = 0; _printf_IP("%sEnd Iteration Loop \n", cReplSpaces(pObj->iStackSize) ); pObj->iStackSize--; if(pObj->iStackSize > 0){ _printf_IP("%sPopUp Stack \n", cReplSpaces(pObj->iStackSize)); if(pObj->iStackSize > 0){ pStackPos--; } else break; continue; } else break; } else { swap( (pObj->cPermCArray + pStackPos->l), (pObj->cPermCArray + pStackPos->i) ); lp = pStackPos->l + 1; rp = pStackPos->r; } }; if( (pObj->iStackSize + 1 ) > pObj->iStackMemSize ){ printf("%s","Grow Stack\n"); int iNewStackMemSize = pObj->iStackMemSize + STACK_PERMITERDATA_GROW; PermIterData_t* pStackRealloc = (PermIterData_t*) realloc( pObj->pStack, iNewStackMemSize * sizeof(PermIterData_t) ); if(!pStackRealloc){ pObj->iStackSize = 0;//Algorithm Termination Immediately break; } else { pObj->pStack = pStackRealloc; pObj->iStackMemSize = iNewStackMemSize; }; } pObj->iStackSize++; pStackPos++; pStackPos->l = lp; pStackPos->r = rp; pStackPos->i = pStackPos->l; pStackPos->bLoop = 0; _printf_IP("%sPush Stack: { a = \"%s\", l = %i, r = %i } \n", cReplSpaces(pObj->iStackSize), pObj->cPermCArray, pStackPos->l, pStackPos->r ); } }; return retstr; } int PermCArrayGen_destroy( PermCArrGen_t** ppObj ){ if(ppObj == NULL)return 0; if(*ppObj == NULL)return 0; PermCArrGen_t* pObj = *ppObj; int iFreeRes = 0; if(pObj->pStack){ free(pObj->pStack); pObj->pStack = NULL; }; if(pObj->cPermCArray){ free(pObj->cPermCArray); pObj->cPermCArray = NULL; }; if(*ppObj){ free(*ppObj); *ppObj = NULL; }; iFreeRes = 1; return iFreeRes; } int CmbStrSortArray_create(CmbStrSortArray_t** ppArr, int n) { if(ppArr == NULL)return 0; *ppArr = (CmbStrSortArray_t*)calloc(1, sizeof(CmbStrSortArray_t) ); if( !(*ppArr) ){ return 0; }; int iRes = 1; CmbStrSortArray_t* pArr = *ppArr; pArr->iCmbStrLen = n; pArr->iaCmbStrsMemSize = GROW_SORTEDARRAY_CMBSTR; pArr->iaCmbStrsSize = 0; pArr->aCmbStrs = (char*) calloc(pArr->iaCmbStrsMemSize, (pArr->iCmbStrLen + 1) ); if( !(pArr->aCmbStrs) ){ iRes = 0; free(*ppArr); *ppArr = NULL; }; return iRes; } int CmbStrSortArray_destroy(CmbStrSortArray_t** ppArr) { if(ppArr == NULL)return 0; if(*ppArr == NULL)return 0; int iFreeRes = 0; CmbStrSortArray_t* pArr = *ppArr; if(pArr->aCmbStrs){ free(pArr->aCmbStrs); pArr->aCmbStrs = NULL; }; if(*ppArr){ free(*ppArr); *ppArr = NULL; }; iFreeRes = 1; return iFreeRes; } void CmbStrSortArray_print( CmbStrSortArray_t* pArr ){ if(pArr == NULL)return; printf("CmbStrSortArray {\n"); for( int i = 0; i < pArr->iaCmbStrsMemSize; i++){ if( i < pArr->iaCmbStrsSize ){ printf(" \"%s\",", (pArr->aCmbStrs + (pArr->iCmbStrLen + 1 )*i) ); }else{ printf(" NULL,"); }; }; printf(" }\n"); } int CmbStrSortArray_add(CmbStrSortArray_t *pCmbStrSortArray, char* cmbstr) { if(pCmbStrSortArray == NULL)return 0; if(cmbstr == NULL)return 0; if(strlen(cmbstr) != pCmbStrSortArray->iCmbStrLen)return 0; char *pPos; int bAddedNew = 0; int bError = 0; if( pCmbStrSortArray->iaCmbStrsSize == 0 ){ pCmbStrSortArray->iaCmbStrsSize++; memcpy(pCmbStrSortArray->aCmbStrs, cmbstr, pCmbStrSortArray->iCmbStrLen + 1); bAddedNew = 1; } else { if( pCmbStrSortArray->iaCmbStrsSize == 1 ){ if( memcmp(pCmbStrSortArray->aCmbStrs, cmbstr, pCmbStrSortArray->iCmbStrLen) == 0 ){ //Equal - Ignore } else if( memcmp(pCmbStrSortArray->aCmbStrs, cmbstr, pCmbStrSortArray->iCmbStrLen) < 0 ){ //Grate of exist - Insert to Pos 2 pCmbStrSortArray->iaCmbStrsSize++; pPos = pCmbStrSortArray->aCmbStrs + (pCmbStrSortArray->iCmbStrLen + 1); memcpy(pPos, cmbstr, pCmbStrSortArray->iCmbStrLen + 1); bAddedNew = 1; } else if( memcmp(pCmbStrSortArray->aCmbStrs, cmbstr, pCmbStrSortArray->iCmbStrLen) > 0 ){ //Low of exist - Move Elem to Pos 2 and Insert to Pos 1 pCmbStrSortArray->iaCmbStrsSize++; memmove( pCmbStrSortArray->aCmbStrs + (pCmbStrSortArray->iCmbStrLen + 1), pCmbStrSortArray->aCmbStrs, (pCmbStrSortArray->iCmbStrLen + 1) ); pPos = pCmbStrSortArray->aCmbStrs; memcpy(pPos, cmbstr, pCmbStrSortArray->iCmbStrLen + 1); bAddedNew = 1; }; } else { int iLeftIdx = 0; int iRightIdx = pCmbStrSortArray->iaCmbStrsSize - 1; int iDx; char *pPosCenter; char *pPosLeft; char *pPosRight; while( !bError ){ iDx = (iRightIdx - iLeftIdx); if( iDx == 1 ){ pPosLeft = pCmbStrSortArray->aCmbStrs + (pCmbStrSortArray->iCmbStrLen + 1) * iLeftIdx; pPosRight = pCmbStrSortArray->aCmbStrs + (pCmbStrSortArray->iCmbStrLen + 1) * iRightIdx; if( memcmp( pPosLeft, cmbstr, pCmbStrSortArray->iCmbStrLen) == 0 ){ //Equal - Ignore } else if( memcmp( pPosRight, cmbstr, pCmbStrSortArray->iCmbStrLen) == 0 ){ //Equal - Ignore } else { if( pCmbStrSortArray->iaCmbStrsSize + 1 == pCmbStrSortArray->iaCmbStrsMemSize ){ int iNewMemSize = pCmbStrSortArray->iaCmbStrsMemSize + GROW_SORTEDARRAY_CMBSTR; size_t iMemSize = iNewMemSize * (pCmbStrSortArray->iCmbStrLen + 1); char* pPtrRealloc = (char*)realloc( pCmbStrSortArray->aCmbStrs, iMemSize ); if( !pPtrRealloc ){ bError = 1; break; } else { pCmbStrSortArray->iaCmbStrsMemSize = iNewMemSize; pCmbStrSortArray->aCmbStrs = pPtrRealloc; pPosLeft = pCmbStrSortArray->aCmbStrs + (pCmbStrSortArray->iCmbStrLen + 1) * iLeftIdx; pPosRight = pCmbStrSortArray->aCmbStrs + (pCmbStrSortArray->iCmbStrLen + 1) * iRightIdx; }; }; if( memcmp( pPosRight, cmbstr, pCmbStrSortArray->iCmbStrLen) < 0 ){ //Grate of Right // Move All after Right and Insert to Right Pos + 1 pCmbStrSortArray->iaCmbStrsSize++; if( iRightIdx < pCmbStrSortArray->iaCmbStrsSize - 1) { memmove( pPosRight + (pCmbStrSortArray->iCmbStrLen + 1)*2, pPosRight + (pCmbStrSortArray->iCmbStrLen + 1), ( pCmbStrSortArray->iaCmbStrsSize - (iRightIdx + 1) ) * ( pCmbStrSortArray->iCmbStrLen + 1) ); }; pPos = pCmbStrSortArray->aCmbStrs; memcpy( pPosRight + (pCmbStrSortArray->iCmbStrLen + 1), cmbstr, pCmbStrSortArray->iCmbStrLen + 1); bAddedNew = 1; } else if( memcmp( pPosLeft, cmbstr, pCmbStrSortArray->iCmbStrLen) > 0 ){ //Low of Left // Move All after Left include Left and Insert to Left Pos pCmbStrSortArray->iaCmbStrsSize++; memmove( pPosLeft + (pCmbStrSortArray->iCmbStrLen + 1), pPosLeft, ( pCmbStrSortArray->iaCmbStrsSize - iLeftIdx )* ( pCmbStrSortArray->iCmbStrLen + 1) ); pPos = pCmbStrSortArray->aCmbStrs; memcpy( pPosLeft, cmbstr, pCmbStrSortArray->iCmbStrLen + 1); bAddedNew = 1; } else { //Grate of Left and Low of Right // Move All after Right include Right and Insert to Right Pos pCmbStrSortArray->iaCmbStrsSize++; memmove( pPosRight + (pCmbStrSortArray->iCmbStrLen + 1), pPosRight, ( pCmbStrSortArray->iaCmbStrsSize - iRightIdx ) * ( pCmbStrSortArray->iCmbStrLen + 1) ); pPos = pCmbStrSortArray->aCmbStrs; memcpy( pPosRight, cmbstr, pCmbStrSortArray->iCmbStrLen + 1); bAddedNew = 1; }; }; break; }; iDx = iDx >> 1; pPosCenter = pCmbStrSortArray->aCmbStrs + (pCmbStrSortArray->iCmbStrLen + 1) * ( iLeftIdx + iDx ); if( memcmp( pPosCenter, cmbstr, pCmbStrSortArray->iCmbStrLen) == 0 ){ //Equal - Ignore break; } else if( memcmp( pPosCenter, cmbstr, pCmbStrSortArray->iCmbStrLen) < 0 ){ //Grate of Center iLeftIdx = iLeftIdx + iDx; } else if( memcmp( pPosCenter, cmbstr, pCmbStrSortArray->iCmbStrLen) > 0 ){ //Low of Center iRightIdx = iLeftIdx + iDx; }; }; }; }; return bAddedNew; }

Finding the string when viewing a permutation iterator of the string with a Unique Permutation Cache