/*
 * File:   main.c
 * Author: Duy
 *
 * Created on 2. května 2016, 19:53
 */

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

/*
 *
 */
int n;
int koef = 1;
char input[20];

int factorial(int n) {
    int i;
    int fact = 1;
    for (i = 1; i <= n; i++) {
        fact = fact*i;
    }
    return fact;
}

void checkRepetition(int zacatek, int konec, int index, char *pole) {
    int i;
    int counter = 0;
    for (i = zacatek; i < konec; i++) {
        if (pole[i] == pole[index]) {
            counter++;
            // printf("ANO  %d\n", counter);

        } else {
            // printf("NE  %d\n", counter);
            //  printf(" nerovnam se index %d pozice %d\n", index, i);
            koef = koef * (factorial(counter));
            checkRepetition(i, konec, i, pole);
            break;
        }

        if (i == konec - 1) {
            koef = koef * (factorial(counter));
        }
    }
    // printf(" dosel jsem na konec index %d\n", index);
    //koef = koef * (factorial(counter));
}

void swap(char* i, char* j) {
    char tmp = *i;
    *i = *j;
    *j = tmp;
    //implement code
}

void adaptedBubbleSort(char *pole, int velikost) {
    char *tmppole = pole;
    int i, j;
    for (i = 0; i < velikost; i++) {

        int sorted = 0;
        for (j = 0; j < velikost - 1; j++) {
            if (tmppole[j] > tmppole[j + 1]) {
                sorted = 1;
                swap(&tmppole[j], &tmppole[ j + 1]);
            }
        }
        if (sorted == 0) {
            break;
        }
    }
}

int next_permutation(char *pole, int velikost) {// algoritmus inspirovany https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
    int tmp;


    int i;
    if (velikost <= 0)
        return 0;
    i = velikost - 1;
    while (i > 0 && pole[i - 1] >= pole[i])
        i--;
    if (i == 0)
        return 0;


    int j;
    j = velikost - 1;
    while (pole[j] <= pole[i - 1])
        j--;
    tmp = pole[i - 1];
    pole[i - 1] = pole[j];
    pole[j] = tmp;


    j = velikost - 1;
    while (i < j) {
        tmp = pole[i];
        pole[i] = pole[j];
        pole[j] = tmp;
        i++;
        j--;
    }
    return 1;
}

int main(int argc, char** argv) {
    // printf("zadej retezec\n");
    scanf("%s", input); // pole se stejne predava jako reference, ale radsi si napisu & abych si pamatoval ze se ma predavat adresa
    //printf("velikost retezce je %d\n", (strlen(input)));
    // printf("retezec pred ukoncenim %s\n", input);
    input[8] = '\0';
    // printf("Delka retezce: %d\n", (strlen(input)));
    n = strlen(input);
    printf("Delka retezce: %d\n", n);
    printf("Vstupni retezec: \"%s\"\n", input);
    /*if (input[0] > input[1])
        printf("prvni znak je vetsi nez druhy");
    else
        printf("neni vetsi");*/
    int velikost = ((sizeof (char)) * n + 1);
    char *pointernapole = (char*) malloc(velikost);
    //printf("velikost alokovane pameti je %d\n", velikost);
    if (pointernapole == NULL) {
        printf("Chyba pri alokaci\n");
        return 1;
    }
    int i;
    for (i = 0; i < n + 1; i++) {
        pointernapole[i] = input[i];
    }
    //pointernapole[n] = '\0';
    //printf(" dynamicky alokovane pole %s\n", pointernapole);
    adaptedBubbleSort(pointernapole, n);
    checkRepetition(0, n, 0, pointernapole);
    //printf("koeficient je %d\n", koef);

    //printf("tisknu permutace\n");
    printf("Serazeno: \"%s\"\n", pointernapole);
    printf("Pocet permutaci: %d\n", factorial(n));

    for (i = 0; i < koef; i++) {
        printf("\"%s\"\n", pointernapole);
    }

    while (next_permutation(pointernapole, n)) {
        for (i = 0; i < koef; i++) {
            printf("\"%s\"\n", pointernapole);
        }
    }


    free(pointernapole);

    return 0;
}