Thread: Permutations Problem Help

Originally Posted by john.c

It's pretty easy to write a brute force solution. Recursion isn't needed.

Code:

#include <stdio.h>
#include <string.h>
 
void print_segmented_strings(const char *s, int len) {
    printf("%s:\n", s);
 
    // Loop through all possible division points.
    for (int i = 1; i < len - 1; ++i)
        for (int j = i + 1; j < len; ++j) {
 
            // Check that the segments contain the same number of a's.
            int cnt1 = 0, cnt2 = 0, cnt3 = 0;
            for (int k = 0; k < i;   ++k) if (s[k] == 'a') ++cnt1;
            for (int k = i; k < j;   ++k) if (s[k] == 'a') ++cnt2;
            if (cnt1 != cnt2) continue;
            for (int k = j; k < len; ++k) if (s[k] == 'a') ++cnt3;
            if (cnt2 != cnt3) continue;
 
            // Print the segmented string.
            printf("    (");
            for (int k = 0; k < i;   ++k) putchar(s[k]);
            printf(",");
            for (int k = i; k < j;   ++k) putchar(s[k]);
            printf(",");
            for (int k = j; k < len; ++k) putchar(s[k]);
            printf(")\n");
        }
}
 
int main() {
    const char *s[] = {
        "ababa",
        "bbbbb",
        "ababb",
        "baababbbabaababbaa",
        "abababababa",
        "aaaaaa",
        NULL
    };
 
    for (int i = 0; s[i]; ++i)
        print_segmented_strings(s[i], strlen(s[i]));
 
    return 0;
}

Output:

Code:

ababa:
    (a,ba,ba)
    (a,bab,a)
    (ab,a,ba)
    (ab,ab,a)
bbbbb:
    (b,b,bbb)
    (b,bb,bb)
    (b,bbb,b)
    (bb,b,bb)
    (bb,bb,b)
    (bbb,b,b)
ababb:
baababbbabaababbaa:
    (baaba,bbbabaa,babbaa)
    (baaba,bbbabaab,abbaa)
    (baabab,bbabaa,babbaa)
    (baabab,bbabaab,abbaa)
    (baababb,babaa,babbaa)
    (baababb,babaab,abbaa)
    (baababbb,abaa,babbaa)
    (baababbb,abaab,abbaa)
abababababa:
    (aba,baba,baba)
    (aba,babab,aba)
    (abab,aba,baba)
    (abab,abab,aba)
aaaaaa:
    (aa,aa,aa)

Originally Posted by john.c

@rusy,

I think you are taking the word "permutations" too seriously and misunderstanding the problem. It doesn't really have anything to do with permutations. The OP is mistaken in using that word.

I believe that my answer is correct, but since the OP has apparently ignored it, we may never know.

I believe I answered you by "appreciated" , it means that you given me the correct answer !

Really appreciated and thanks for your advance!


Alright I misused the word permutations in my problem, and appreciate if you could give any assistance in my next thread.


Thanks.