Перестановка всех цифр в числе. Си

Question

Сделал функцию которая перебирает все цифры в числе, но некоректно, если ввести 123, то все хорошо и как и должно быть 6 вариантов перестановок, но если ввожу 1234, то вместо того чтобы вывести 24 варианта перестановок, выводит значительно больше, как я заметил несколько раз выводит ту или иную перестановку. Помогите это исправить.

#include <stdio.h>
#define N 10
#define SWAP(a,b) {int temp = a; a = b; b = temp;}

void perm(char str[],int count)
{
    for(int i = 0; i < count; i++){
        for(int j=0;j<count-1;j++){
            printf("%s\n",str);
            SWAP(str[j],str[j + 1])
            perm(str,count-2);
        }
    }
}

int main()
{
    char str[N]="";
    int count=0;
    printf("Enter a number:\n");
    gets(str);
    while(str[count]){
        count++;
    }
    printf("res:\n");
    perm(str, count);
    return 0;
}

Answer 1

Чисто по числу операций не похоже, что данный код в целом делает n! перестановок.

Можно предложить следующее: на каждом уровне рекурсии выполняется ровно count обменов последнего элемента с другими, в том числе и с собой же (фактически отсутствие обмена)

void perm(char str[], int count)
{
    if (count == 0)
        printf("%s\n", str);
    else
        for (int i = 0; i < count; i++) {
            SWAP(str[i], str[count - 1]);
            perm(str, count - 1);
            SWAP(str[i], str[count - 1]);//возвращаем назад
        }
}

БЛОГ НА HUSL

Перестановка всех цифр в числе. Си

Ответы (1 шт):