лексикографически следующая перестановка строк - PullRequest
Новая
       8

лексикографически следующая перестановка строк

0 голосов
/ 02 апреля 2020

Я пытаюсь написать следующую функцию перестановки. Эта функция изменяет массив s строк до следующей перестановки в лексикографическом порядке c. Возвращает 0, если нет следующей перестановки, и 1 в противном случае.

Мой код: 

int next_permutation(int n, char **s) {
    int i, j;

    for (i = n - 1; i >= 0; i--) {
        if (strcmp(s[i], s[i - 1]) > 0) {
            //find smallest string bigger than s[i - 1] and swap
            j = i - 1;
            char *min_max = malloc(11 * sizeof(char));

            int k;
            for (k = i; k < n; k++) {
                if (strcmp(s[j], s[k]) < 0) {
                    strcpy(min_max, s[k]);
                } else {
                    break;
                }
            }
            strcpy(s[k - 1], s[j]);
            strcpy(s[j], min_max);

            //sort the tail in increasing order
            int end = n - 1;
            while (i < end) {
                strcpy(min_max, s[i]);
                strcpy(s[i], s[end]);
                strcpy(s[end], min_max);
                i++;
                end--;
            }
            break;
        } else {
            continue;
        }
    }

    if (i == 0) {
        return 0;
    } else {
        return 1;
    }
}

Здесь n - количество элементов в строковом массиве s.

Мой код не работает. Это ошибка сегментации. Буду признателен за любую помощь. Я новичок, поэтому вы можете предложить мне другие улучшения в моем коде. 

 Reading symbols from Solution...done.

    [New LWP 12426]

    [Thread debugging using libthread_db enabled]

    Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

    Core was generated by `./Solution'.

    Program terminated with signal SIGSEGV, Segmentation fault.

    #0  __strcmp_avx2 () at ../sysdeps/x86_64/multiarch/strcmp-avx2.S:102

1 Ответ

0 голосов
/ 02 апреля 2020

Я думаю, это из-за вашей последней итерации по вашему l oop. Ваш последний индекс в для l oop равен i = 0, а в if(strcmp(s[i], s[i - 1]) > 0) вы пытаетесь найти s[-1], что вы не можете сделать в C, и это недопустимое значение (и, следовательно, ошибка сегментации) .

...