Global variable not behaving as expected

Question

That is the problem I'm trying to solve. (Given a 2n length string of distinct characters I have to divide it in 2 parts in all possible ways without repeating groups).

The method I used is:

Generate all permutations of string.
Store acceptable permutations (I am generating "hauy" and "hayu" both but only storing one of them).
Check newly generated permutations against stored ones to filter out duplicates.
Print

(I realize that there might be better ways of doing this)

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

char *b[100000000];
int bSize = 0;
void print(char *a)
{   
    int k = strlen(a);
    printf("M: ");
    for(int i=0 ; i<k/2 ; i++)
    {
        printf("%c ", a[i]);
    }
    printf("| B: ");
    for(int i=0 ; i<k/2 ; i++)
    {
        printf("%c ", a[k/2 + i]);
    }
    printf("\n");
}
void check(char *a)
{
    int k = strlen(a);
    for(int i=0 ; i<bSize ; i++)
    {
        int c = 0;
        for(int j=0 ; j<k/2 ; j++)
        {
            for(int m=0 ; m<k/2 ; m++)
            {
                if(a[m] == b[i][j])
                {
                    c++;
                    break;
                }
            }
        }
        for(int j=0 ; j<k/2 ; j++)
        {
            for(int m=0 ; m<k/2 ; m++)
            {
                if(a[m + k/2] == b[i][j + k/2])
                {
                    c++;
                    break;
                }
            }
        }
        if(c == k)
        {   
            break;
        }
        else
        {
            b[bSize] = a;
            bSize++;
            print(a);
        }
    }
}
void swap(char *a, char *b)
{
    char temp = *a;
    *a = *b;
    *b = temp;
}
void permute(char *a, int start, int end)
{
    if(start == end)
        if(bSize == 0)
        {
            print(a);
            b[bSize] = a;
            bSize++;
        }
        else
            check(a);
    else
    {
        for(int i=start ; i<=end ; i++)
        {
            swap((a+start), (a+i));
            permute(a, start+1, end);
            swap((a+start), (a+i));
        }
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    char f;
    scanf("%c", &f);
    char A[n];
    for(int i=0 ; i<n-2 ; i++)
    {
        char c;
        scanf("%c", &c);
        if(c == ' ' || c == 'M' || c == 'B')
            i--;
        else
            A[i] = c;
    }
    A[n-2] = '\0';
    permute(A, 0, n-3);
    return 0;
}

When I run this only 1 line is given as output. I think the error is with b[]. In the check function b[0] and a always turn out to be equal. And bSize never goes beyond 1. I am unable to understand why.

You don't want permutations. https://stackoverflow.com/a/506841/918959 — Antti Haapala -- Слава Україні, Sep 22 '19 at 08:41
When you say `b[bSize] = a`, you store a pointer to the first element to `A` in `main`, and that's always the same array -- only its contents change when you permute. You can verify this by printing all `b[i]` -- it's always the current permutation. If you want to store the current permutation, you must make a copy. — M Oehm, Sep 22 '19 at 08:56

score 0 · Accepted Answer · answered Sep 22 '19 at 09:39

b[bSize] = a; stores the value of a in b[bSize]. a is a pointer to the first element of the array A defined in main. So you are not storing individual strings, just a pointer to A, and that pointer never changes.

To use this algorithm, you must copy each string. That requires changes to how b is defined and how strings are compared. (You cannot compare strings with ==.)

(There is however, a much better algorithm for this task that does not require generating all permutations.)

Global variable not behaving as expected

1 Answers1