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

struct tag {
    char str[4];
};

void swap(struct tag *a, int i, int j) 
{
    struct tag temp = a[i]; a[i] = a[j]; a[j] = temp;
} 

void do_permute(struct tag *tag, int lo, int hi) 
{
    if (lo == hi) { 
        for (int i = 0; i < hi; i++) {
            if (i) printf(" ");
            printf("%s", tag[i].str);
        }
        
        printf("\n"); 
    } else { 
        for (int i = lo; i < hi; i++) { 
            swap(tag, lo, i); 
            do_permute(tag, lo + 1, hi); 
            swap(tag, lo, i); 
       } 
    } 
}

void permute(const char *str)
{
    int l = strlen(str);
    struct tag *tag = malloc(l * sizeof(*tag));
    int count[256] = {0};
    
    // first pass: assign individual indices for each letter
    
    for (int i = 0; i < l; i++) {
        unsigned char k = str[i];
        
        count[k]++;
        snprintf(tag[i].str, sizeof(tag[i].str), "%c%d", str[i], count[k]);
    }
    
    // second pass: remove index for single instances
    
    for (int i = 0; i < l; i++) {
        unsigned char k = str[i];
        
        if (count[k] == 1) tag[i].str[1] = '\0';
    }
    
    do_permute(tag, 0, l);
    
    free(tag);
}

int main(void) 
{ 
    permute("TATTOO"); 

    return 0; 
}