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

/*
 *                            COPYRIGHT
 *
 *  kneck.c
 *  Copyright (C) 2016 Exstrom Laboratories LLC
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  A copy of the GNU General Public License is available on the internet at:
 *  http://www.gnu.org/copyleft/gpl.html
 *
 *  or you can write to:
 *
 *  The Free Software Foundation, Inc.
 *  675 Mass Ave
 *  Cambridge, MA 02139, USA
 *
 *  Exstrom Laboratories LLC contact:
 *  stefan(AT)exstrom.com
 *
 *  Exstrom Laboratories LLC
 *  Longmont, CO 80503, USA
 *
 *
 * The algorithm used in this program can be found in the paper:
 * Generating Necklaces
 * Frank Ruskey and Carla Savage
 *
 */

// Compile: gcc -lm -o kneck kneck.c

void printneck(int *a, int n)
{
  int j;
  for(j=1; j<=n; ++j) printf("%1d", a[j]);
  printf("\n");
}

/*******************************************************************/

int main( int argc, char *argv[] )
{
  if(argc < 3)
    {
      printf("usage: %s k n\n", argv[0]);
      printf("  Generates all k-ary necklaces of length n.\n");
      exit(-1);
    }

  int i, j;
  int k = atoi(argv[1]);
  int n = atoi(argv[2]);
  int *a = (int *)calloc(n+1,sizeof(int));
  printneck(a, n);

  for(i=n; i>0;){
    ++a[i];
    for(j=1; j<=n-i; ++j) a[i+j] = a[j];
    if(n%i == 0) printneck(a, n);
    i = n;
    while(a[i]==k-1) --i;}

  free(a);
  return(0);
}