I am trying to make a program where the user enters a given alphabet and length, and the program generates all possible combinations until the correct combination is met. So if a user inputs: abcd 3 dddd the program will output:

aaaa
aaab
aaac
...
dddb
dddc
dddd
found!!

or if not found just print all combinations then output not found

I am looking at this example I got online but it doesn't return anything to main for me to match with the given input:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void printAllKLengthRec(char set[], char prefix[], int n, int k);

void printAllKLengthRec(char set[], char prefix[], int n, int k) {
    if (k == 0) {
        printf("%s\n", prefix);
        return;
    }
    for (int i = 0; i < n;   i) {
        char *newPrefix = (char *)malloc(n   1);
        char cToStr[] = {set[i], '\0'};
        strcpy(newPrefix, prefix);
        strcat(newPrefix, cToStr);
        printAllKLengthRec(set, newPrefix, n, k - 1);
        free(newPrefix);
    }
}
const int bufsize = 256;

int main () {
    char alphabet[bufsize];
    int len;
    printf("Enter alphabet and length:\n");
    scanf("%s %d", alphabet, &len);

    int alphalen = strlen(alphabet);

    printAllKLengthRec(alphabet, (char *)"", alphalen, len);
}

CodePudding user response：

I am trying to make a program where the user enters a given alphabet and length, and the program generates all possible combinations until the correct combination is met.

If you want to match against a given combination, you should at least read it. So, your scanf call should look like:

scanf("%s %d %s", alphabet, &len, password);

Then, you have to pass it to printAllKLengthRec and compare it with prefix when k == 0. Function printAllKLengthRec may return an int to signal the caller there was a match with password.

Also, since you decided the max buffer length should be 256, you can avoid calling malloc by using a stack buffer to store the current combination:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int printAllKLengthRec(char const* alphabet, char* prefix, char const* password,
                       size_t alphabetLen, size_t passwordLen, size_t k) {
    if (k == 0) {
        printf("%s\n", prefix);
        return (strncmp(prefix, password, passwordLen) == 0);
    }

    int found = 0;
    for (size_t i = 0; i < alphabetLen;   i) {
        prefix[passwordLen - k] = alphabet[i];
        found = printAllKLengthRec(alphabet, prefix, password, alphabetLen, passwordLen, k - 1);
        if (found) break;
    }

    return found;
}

const int bufsize = 256;

int main() {
    char alphabet[bufsize];
    char password[bufsize];

    /* initialize your variables */
    memset(alphabet, '\0', bufsize);
    memset(password, '\0', bufsize);
    int len = 0;

    printf("Enter alphabet, length and password:\n");
    scanf("%s %d %s", alphabet, &len, password);
    /* NOTE here you may:
     *  - evaluate len as strlen(password);
     *  - or check if the input length is actually strlen(password).
     */


    /* Use a buffer to avoid messing with malloc() in printAllKLengthRec */
    char prefix[bufsize];
    memset(prefix, '\0', bufsize);

    size_t const alphalen = strlen(alphabet);
    if (printAllKLengthRec(alphabet, prefix, password, alphalen, len, len))
        puts("found");
    else
        puts("not found");
}

CodePudding user response：

Given:

1. an alphabet (e.g. a-z) that has a length alflen of 26
2. a combination length (e.g.) comblen of 4

We want to simulate a base alflen number that is comblen digits wide. We call it bignum [an int array of length comblen].

Each digit in bignum is an index into the alphabet string.

Here is some refactored code. It is annotated. It's based on code I've used in the past to increment through a base N number of a given number of digits.

It doesn't have a comparison, but, the main issue is the enumeration of all the strings. Adding a compare should be easy.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int alflen;                             // number of chars in alphabet
const char *alfbet;                     // entire alphabet (length is alflen)
int comblen;                            // number of chars per output word

int *bignum;                            // a number that is comblen digits wide

char *bigbuf;                           // buffer large enough for printing
int prtlen;                             // current output print length

// print -- print a combination
void
print(void)
{

    // each bignum value is an index into the alfbet string
    for (int bigidx = 0;  bigidx < comblen;    bigidx)
        bigbuf[bigidx] = alfbet[bignum[bigidx]];

    // add string terminator
    bigbuf[comblen] = 0;

    // do some nice pretty printing
    if ((78 - prtlen) < (comblen   1)) {
        printf("\n");
        prtlen = 0;
    }
    prtlen  = 1;
    prtlen  = comblen;

    // output seperater
    fputc(' ',stdout);

    // output the current word/string
    fputs(bigbuf,stdout);
}

// inc -- increment the "big" number by 1
// RETURNS: carry out (if non-zero we are done)
int
inc(void)
{
    int carry = 1;

    // increment the number digit-by-digit
    for (int bigidx = 0;  bigidx < comblen;    bigidx) {
        if (! carry)
            break;

        // increment the current number digit
        int digit = bignum[bigidx];
        digit  = carry;
        bignum[bigidx] = digit % alflen;

        // get carry out for next digit/column
        carry = digit / alflen;
    }

    return carry;
}

int
main(int argc,char **argv)
{

    --argc;
      argv;

    if (argc != 2) {
        printf("usage: alphabet length\n");
        exit(1);
    }

    // get the alphabet string
    alfbet = argv[0];

    // get number of chars in the alphabet
    alflen = strlen(alfbet);

    // get the width of the output words
    comblen = atoi(argv[1]);

    // allocate the base alflen number that is comblen digits wide
    bignum = calloc(comblen,sizeof(*bignum));

    // get the print buffer
    bigbuf = malloc(comblen   1);

    while (1) {
        // print the current "number"
        print();

        // increment the number until we overflow
        if (inc())
            break;
    }

    if (prtlen > 0)
        printf("\n");

    return 0;
}

Doing a full output for abcdefghijklmnopqrstuvwxyz 4 would generate too much output to fit here.

But, there is no limit to the alphabet size or combination length.

For the arguments: abcdef 4, the output is:

 aaaa baaa caaa daaa eaaa faaa abaa bbaa cbaa dbaa ebaa fbaa acaa bcaa ccaa
 dcaa ecaa fcaa adaa bdaa cdaa ddaa edaa fdaa aeaa beaa ceaa deaa eeaa feaa
 afaa bfaa cfaa dfaa efaa ffaa aaba baba caba daba eaba faba abba bbba cbba
 dbba ebba fbba acba bcba ccba dcba ecba fcba adba bdba cdba ddba edba fdba
 aeba beba ceba deba eeba feba afba bfba cfba dfba efba ffba aaca baca caca
 daca eaca faca abca bbca cbca dbca ebca fbca acca bcca ccca dcca ecca fcca
 adca bdca cdca ddca edca fdca aeca beca ceca deca eeca feca afca bfca cfca
 dfca efca ffca aada bada cada dada eada fada abda bbda cbda dbda ebda fbda
 acda bcda ccda dcda ecda fcda adda bdda cdda ddda edda fdda aeda beda ceda
 deda eeda feda afda bfda cfda dfda efda ffda aaea baea caea daea eaea faea
 abea bbea cbea dbea ebea fbea acea bcea ccea dcea ecea fcea adea bdea cdea
 ddea edea fdea aeea beea ceea deea eeea feea afea bfea cfea dfea efea ffea
 aafa bafa cafa dafa eafa fafa abfa bbfa cbfa dbfa ebfa fbfa acfa bcfa ccfa
 dcfa ecfa fcfa adfa bdfa cdfa ddfa edfa fdfa aefa befa cefa defa eefa fefa
 affa bffa cffa dffa effa fffa aaab baab caab daab eaab faab abab bbab cbab
 dbab ebab fbab acab bcab ccab dcab ecab fcab adab bdab cdab ddab edab fdab
 aeab beab ceab deab eeab feab afab bfab cfab dfab efab ffab aabb babb cabb
 dabb eabb fabb abbb bbbb cbbb dbbb ebbb fbbb acbb bcbb ccbb dcbb ecbb fcbb
 adbb bdbb cdbb ddbb edbb fdbb aebb bebb cebb debb eebb febb afbb bfbb cfbb
 dfbb efbb ffbb aacb bacb cacb dacb eacb facb abcb bbcb cbcb dbcb ebcb fbcb
 accb bccb cccb dccb eccb fccb adcb bdcb cdcb ddcb edcb fdcb aecb becb cecb
 decb eecb fecb afcb bfcb cfcb dfcb efcb ffcb aadb badb cadb dadb eadb fadb
 abdb bbdb cbdb dbdb ebdb fbdb acdb bcdb ccdb dcdb ecdb fcdb addb bddb cddb
 dddb eddb fddb aedb bedb cedb dedb eedb fedb afdb bfdb cfdb dfdb efdb ffdb
 aaeb baeb caeb daeb eaeb faeb abeb bbeb cbeb dbeb ebeb fbeb aceb bceb cceb
 dceb eceb fceb adeb bdeb cdeb ddeb edeb fdeb aeeb beeb ceeb deeb eeeb feeb
 afeb bfeb cfeb dfeb efeb ffeb aafb bafb cafb dafb eafb fafb abfb bbfb cbfb
 dbfb ebfb fbfb acfb bcfb ccfb dcfb ecfb fcfb adfb bdfb cdfb ddfb edfb fdfb
 aefb befb cefb defb eefb fefb affb bffb cffb dffb effb fffb aaac baac caac
 daac eaac faac abac bbac cbac dbac ebac fbac acac bcac ccac dcac ecac fcac
 adac bdac cdac ddac edac fdac aeac beac ceac deac eeac feac afac bfac cfac
 dfac efac ffac aabc babc cabc dabc eabc fabc abbc bbbc cbbc dbbc ebbc fbbc
 acbc bcbc ccbc dcbc ecbc fcbc adbc bdbc cdbc ddbc edbc fdbc aebc bebc cebc
 debc eebc febc afbc bfbc cfbc dfbc efbc ffbc aacc bacc cacc dacc eacc facc
 abcc bbcc cbcc dbcc ebcc fbcc accc bccc cccc dccc eccc fccc adcc bdcc cdcc
 ddcc edcc fdcc aecc becc cecc decc eecc fecc afcc bfcc cfcc dfcc efcc ffcc
 aadc badc cadc dadc eadc fadc abdc bbdc cbdc dbdc ebdc fbdc acdc bcdc ccdc
 dcdc ecdc fcdc addc bddc cddc dddc eddc fddc aedc bedc cedc dedc eedc fedc
 afdc bfdc cfdc dfdc efdc ffdc aaec baec caec daec eaec faec abec bbec cbec
 dbec ebec fbec acec bcec ccec dcec ecec fcec adec bdec cdec ddec edec fdec
 aeec beec ceec deec eeec feec afec bfec cfec dfec efec ffec aafc bafc cafc
 dafc eafc fafc abfc bbfc cbfc dbfc ebfc fbfc acfc bcfc ccfc dcfc ecfc fcfc
 adfc bdfc cdfc ddfc edfc fdfc aefc befc cefc defc eefc fefc affc bffc cffc
 dffc effc fffc aaad baad caad daad eaad faad abad bbad cbad dbad ebad fbad
 acad bcad ccad dcad ecad fcad adad bdad cdad ddad edad fdad aead bead cead
 dead eead fead afad bfad cfad dfad efad ffad aabd babd cabd dabd eabd fabd
 abbd bbbd cbbd dbbd ebbd fbbd acbd bcbd ccbd dcbd ecbd fcbd adbd bdbd cdbd
 ddbd edbd fdbd aebd bebd cebd debd eebd febd afbd bfbd cfbd dfbd efbd ffbd
 aacd bacd cacd dacd eacd facd abcd bbcd cbcd dbcd ebcd fbcd accd bccd cccd
 dccd eccd fccd adcd bdcd cdcd ddcd edcd fdcd aecd becd cecd decd eecd fecd
 afcd bfcd cfcd dfcd efcd ffcd aadd badd cadd dadd eadd fadd abdd bbdd cbdd
 dbdd ebdd fbdd acdd bcdd ccdd dcdd ecdd fcdd addd bddd cddd dddd eddd fddd
 aedd bedd cedd dedd eedd fedd afdd bfdd cfdd dfdd efdd ffdd aaed baed caed
 daed eaed faed abed bbed cbed dbed ebed fbed aced bced cced dced eced fced
 aded bded cded dded eded fded aeed beed ceed deed eeed feed afed bfed cfed
 dfed efed ffed aafd bafd cafd dafd eafd fafd abfd bbfd cbfd dbfd ebfd fbfd
 acfd bcfd ccfd dcfd ecfd fcfd adfd bdfd cdfd ddfd edfd fdfd aefd befd cefd
 defd eefd fefd affd bffd cffd dffd effd fffd aaae baae caae daae eaae faae
 abae bbae cbae dbae ebae fbae acae bcae ccae dcae ecae fcae adae bdae cdae
 ddae edae fdae aeae beae ceae deae eeae feae afae bfae cfae dfae efae ffae
 aabe babe cabe dabe eabe fabe abbe bbbe cbbe dbbe ebbe fbbe acbe bcbe ccbe
 dcbe ecbe fcbe adbe bdbe cdbe ddbe edbe fdbe aebe bebe cebe debe eebe febe
 afbe bfbe cfbe dfbe efbe ffbe aace bace cace dace eace face abce bbce cbce
 dbce ebce fbce acce bcce ccce dcce ecce fcce adce bdce cdce ddce edce fdce
 aece bece cece dece eece fece afce bfce cfce dfce efce ffce aade bade cade
 dade eade fade abde bbde cbde dbde ebde fbde acde bcde ccde dcde ecde fcde
 adde bdde cdde ddde edde fdde aede bede cede dede eede fede afde bfde cfde
 dfde efde ffde aaee baee caee daee eaee faee abee bbee cbee dbee ebee fbee
 acee bcee ccee dcee ecee fcee adee bdee cdee ddee edee fdee aeee beee ceee
 deee eeee feee afee bfee cfee dfee efee ffee aafe bafe cafe dafe eafe fafe
 abfe bbfe cbfe dbfe ebfe fbfe acfe bcfe ccfe dcfe ecfe fcfe adfe bdfe cdfe
 ddfe edfe fdfe aefe befe cefe defe eefe fefe affe bffe cffe dffe effe fffe
 aaaf baaf caaf daaf eaaf faaf abaf bbaf cbaf dbaf ebaf fbaf acaf bcaf ccaf
 dcaf ecaf fcaf adaf bdaf cdaf ddaf edaf fdaf aeaf beaf ceaf deaf eeaf feaf
 afaf bfaf cfaf dfaf efaf ffaf aabf babf cabf dabf eabf fabf abbf bbbf cbbf
 dbbf ebbf fbbf acbf bcbf ccbf dcbf ecbf fcbf adbf bdbf cdbf ddbf edbf fdbf
 aebf bebf cebf debf eebf febf afbf bfbf cfbf dfbf efbf ffbf aacf bacf cacf
 dacf eacf facf abcf bbcf cbcf dbcf ebcf fbcf accf bccf cccf dccf eccf fccf
 adcf bdcf cdcf ddcf edcf fdcf aecf becf cecf decf eecf fecf afcf bfcf cfcf
 dfcf efcf ffcf aadf badf cadf dadf eadf fadf abdf bbdf cbdf dbdf ebdf fbdf
 acdf bcdf ccdf dcdf ecdf fcdf addf bddf cddf dddf eddf fddf aedf bedf cedf
 dedf eedf fedf afdf bfdf cfdf dfdf efdf ffdf aaef baef caef daef eaef faef
 abef bbef cbef dbef ebef fbef acef bcef ccef dcef ecef fcef adef bdef cdef
 ddef edef fdef aeef beef ceef deef eeef feef afef bfef cfef dfef efef ffef
 aaff baff caff daff eaff faff abff bbff cbff dbff ebff fbff acff bcff ccff
 dcff ecff fcff adff bdff cdff ddff edff fdff aeff beff ceff deff eeff feff
 afff bfff cfff dfff efff ffff