Permutations Problem Help

Hi guys,
I'm struggling to solve and implement in C a function that gets as input
a "string" which it contains the chars 'a' or 'b' (the input string might be included chars 'a' and 'b' altogether) , and what the function does is to
divide the string to three parts each permutation/set without having NULL/empty chars at each permutation/set. the length of the
permutation/set isn't necessarily equal, but they all (all the three parts of each set/permutation) have the same
number of occurrence/appearance of chars 'a' .
the function must return the maximum possibilities that we can divide the string by 3 at each possible set/permutation.

Examples:
#1
input string: "ababa" is having 4 possibilities of permutations/sets (as I said each permutations is contains from 3 parts and if there's no 3 parts so this possibility is discarded ! ), in this case the maximum possibilities are:
(ab,a,ba) , (a,bab,a) , (a,ba,ba) ,(ab,ab,a).

#2
input string: "bbbbb" is having 6 possibilities of permutations/sets (as I said each permutations is contains from 3 parts and if there's no 3 parts so this possibility is discarded ! ), in this case the maximum possibilities are: (be careful here 'a' is o has no occurance so at each permutation/set there's no 'a' and it's equal for each set -has no 'a'-)
(bb,b,bb) , (bbb,b,b) , (bb,bb,b) ,(b,bbb,b),(b,bb,bb),(b,b,bbb).

#3
input string:'ababb' is having 0 possibilities, so the function returns empty string or NULL or " " even could return whatever we want which resemble about there's no possibilities for this string.



Im struggling to implement this function in C and Im stuck on it about three days.
I started to think to solve this problem in recursive approach because we are talking about permutations and maximum possibilities.
so I deeply thought and started with my algorithm as this:
first condition is to check :
'a' % 3 == 0 for every 3 parts of one permutation/set . (set consists 3 parts )
and then to think what's the recursive rule for the other condition (the length of string > 3).
but Im stuck and I couldn't complete I don't know how to continue, any help please? the hardest thing is to discover the recursive rule for my problem with its edge conditions.


Any help out?!



thanks alot.

So what would the result of "abababababa" be?
Would it be only those combinations with two 'a's in each set?

Would "aabaa" be the empty set, since there are 4 'a's and those can't be equipartitioned.

Quote:

---

Originally Posted by Salem

So what would the result of "abababababa" be?
Would it be only those combinations with two 'a's in each set?

Would "aabaa" be the empty set, since there are 4 'a's and those can't be equipartitioned.

---

if can't be equipartitioned then the function should return this possibility.

In each set (consist of three parts) , each part of the set should have the same number of occurrence of 'a' for each part of the set.
this means if there's a possibility two parts of the set has occurrence
of 'a' once for each of the two part, and third part doesn't have 'a' occurrence .. so this isn't possibility and we discard it because
we need all the parts of each set (set consists with 3 parts) to have the same number of occurrence of 'a' .


hope I explained it well.

What about the case with 6 'a's in it?

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)

---

Also answered here -> algorithm - C programming Problem - Maximum Partitions - Stack Overflow

Hi , I appreciate much your help @salem , @John.C .
@Salem I din't get an answer there, because if you even read my post their you would understand that what I need is to understand the algorithm in order to implement it.
See please the answers you'd even understand that there's no c solution ! because my point is to understand and not to copy/paste.

Hallo Salem!

To calculate the number of Permutations with 2 elements in a class is with the Forumula of Euler:

Code:

---

n = { (a+b)! /(a! *b!)}

If a string is "aabaa" you have
element_1 = a = 4
element_2 = b = 1

n = { (a+b)! /(a! * b!)}
n = { (4+1)! /(4! * 1!)}
n = { 5! /(4! *1!)}
n = { 120 / 24 * 1)}
n = { 120 / 24)}
n = 5

---

Example "abababababa":
Length of string is 11

Code:

---

element_1 = a = 6
element_2 = b = 5

n = { (a+b)! /(a! * b!)}
n = { (6+5)! /(6! * 5!)}
n = { 11! /(6! *5!)}
n = { 39916800 / 720 * 120)}
n = { 39916800 / 86400)}
n = 462

---

Note that

Code:

---

n = { (6+5)! /(6! * 5!)} is like
n = { (1*2*3*4*5*6*7*8*9*10*11) /(1*2*3*4*5*6  * 1*2*3*4*5 )}
n = { (7*8*9*10*11) /(1*2*3*4*5 )}
n = 462

---

Now you have a binomial coefficient

read as "n choose k"
here as "11 choose 5" (= 462)

If you would have 3 bananas, 3 apples, 2 lemons

and it doesn't matter if

banana1 banana2, apple3 apple2, banana3, apple1, lemon1, lemon2
or
banana3 banana1, apple1 apple3, banana2, apple2, lemon2, lemon1
is the sequence you can take this formula.

So in this example you would have

Code:

---

n = { (a+b+c)! /(a! * b! * c!)}
n = { (3+3+2)! /(3! * 3! * 2!)}
n = { 8! /(3! * 3! * 2!)}
n = { 40320 /(6 * 6! * 2!)}
n =  40320 /72
n = 560

---

Example to use that:

Code:

---

String: "the dog"
7 bytes = 56 bits
decimal:
116 104 101 032 100 111 103
binary:
01110100 01101000 01100101 00100000 01100100 01101111 01100111
encoded:
10101100 00101001 00011101 00000001 00011100 01111110 11100110

26 times 1
30 times 0

---

When you code this with changing the places of 1 and 0:

Code:

---

then n =  { (26 +30)! /(26! * 30!)}
n = 6646448384109072 possible results if you want the crack the code
for to encrypt this string with permutation of the place.

---

Years ago i wrote a program named talarius with a maximum length of
16384 Byte = 131072 bits. But for Win3.11 up to win 98 se. Only 45 people loaded it down.
To make the number of bits greate made no sense, it taked to much time
to create the keyfile:

Code:

---

Bytes....... Bits .......possible permutations
Nibbel........4............6
1.............8............70
2.............16...........12870
4.............32...........6.0108E+8
8.............64...........1.83262E+18
16............128..........2.39511E+37
32............256..........5.76866E+75
64............512..........4.72553E+152
128...........1024.........4.48125e+306
256...........2048.........5.69709e+614
512...........4096.........1.30195e+1231
1024..........8192.........9.61516e+2436
2048..........16384 .......7.41605e+4929
4096..........32768........?????? )
8192..........65536........??????
18384.........131072.......??????

---

A version for linux is on my system
Attachment 16279

Hallo john.c

With the string "ababa" according the formula of Leonhard Euler
you would got 10 possible permutations.
The string have a length from 5 characters.


I think for the first time it is useful to create a loop witch runs from
100 to 99999.
For example number 1 can be use instead of the character "a"
and number 0 instead of character "b"

To show the characters use an array :

Code:

---

char letters[10] } { 'b', 'a', '', '', '', '', '', '', '', ''};

.....any code

printf("%c", letters[i]);
---any code

---

Because the start and the end of the loop need to have
5 digits. Then convert the decimal int value to a string and
only print the number what have only 3 times digit 1 and
two times digit 0:

like
10101 ------> okay; 3times 1 and 2 times 0

11100
00111 (= 111)
01110 (= 1110)

01101
01011
11001
10011
11010
10110

and so on

@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.

Quote:

---

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)

---

---

Quote:

---

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.