Thread: Permutations Problem Help

  1. #1
    Registered User
    Join Date
    Nov 2020
    Posts
    34

    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.
    Last edited by JohnnyOmari; 12-29-2020 at 10:56 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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 you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Quote Originally Posted by Salem View Post
    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.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    What about the case with 6 'a's in it?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    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)
    A little inaccuracy saves tons of explanation. - H.H. Munro

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    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.

  8. #8
    Registered User
    Join Date
    Nov 2018
    Location
    Amberg in upper palatinate, Bavaria
    Posts
    66

    calculate permutations

    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
    Permutations Problem Help-talarius12-jpg
    Last edited by rusyoldguy; 12-31-2020 at 06:19 AM.

  9. #9
    Registered User
    Join Date
    Nov 2018
    Location
    Amberg in upper palatinate, Bavaria
    Posts
    66
    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

  10. #10
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    @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.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  11. #11
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Quote Originally Posted by john.c View Post
    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 View Post
    @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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutations
    By Nominal Animal in forum Tech Board
    Replies: 6
    Last Post: 08-29-2015, 10:43 PM
  2. k-permutations
    By miguel.pinr in forum C Programming
    Replies: 3
    Last Post: 11-27-2012, 05:23 AM
  3. Permutations
    By bumfluff in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2008, 12:33 PM
  4. Permutations
    By kiddy in forum C++ Programming
    Replies: 1
    Last Post: 02-11-2002, 09:53 AM
  5. permutations based problem
    By Zeeshan in forum C++ Programming
    Replies: 3
    Last Post: 11-06-2001, 10:13 AM

Tags for this Thread