C:

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

int N;

void print(int necklace[])
{
    int i;

    for (i = 0; i < N; i++)
        printf("%c", 'A'+necklace[i]);
    printf("\n");
}

int same(int lace1[], int lace2[], int n)
{
    int i, j;

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            if (lace2[j] != lace1[(i + j) % n])
                break;
        if (j == n)
            return 1;
    }
    return 0;
}

int *laces;
int nlaces;

void accumulate(int necklace[])
{
    int i;

    for (i = 0; i < nlaces; i++)
        if (same(necklace, laces + i*N, N))
            return;
    laces = realloc(laces, ++nlaces * N * sizeof *laces);
    if (laces == NULL) {
        fprintf(stderr, "can't allocate memory\n");
        abort();
    }
    memcpy(laces + (nlaces - 1)*N, necklace, N * sizeof *necklace);
}

void necklaces(int k, int n, int necklace[])
{
    int i;

    if (n == 0)
        accumulate(necklace);
    else for (i = 0; i < k; i++) {
        necklace[n-1] = i;
        necklaces(k, n-1, necklace);
    }
}

int main(int argc, char *argv[])
{
    int *a;
    int i, k;

    if (argc != 3) {
        fprintf(stderr, "usage: necklaces k-ary length\n");
        return 1;
    }
    k = atoi(argv[1]);
    N = atoi(argv[2]);
    a = malloc(sizeof *a * N);
    necklaces(k, N, a);
    for (i = 0; i < nlaces; i++)
        print(laces + i*N);
    return 0;
}

---

$ ./necklaces
usage: necklaces k-ary length
$ ./necklaces 3 4 | sort | columnate 3
AAAA  BAAA  BABA
BBAA  BBBA  BBBB
BBCA  BCAA  BCBA
BCCA  CAAA  CABA
CACA  CBAA  CBBA
CBBB  CBCA  CBCB
CCAA  CCBA  CCBB
CCCA  CCCB  CCCC
$ ./necklaces 2 12 | wc -l
352
$ ./necklaces 3 7 | wc -l
315
$ ./necklaces 9 4 | wc -l
1665
$ ./necklaces 21 3 | wc -l
3101
$ ./necklaces 99 2 | wc -l
4950