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

/*
 *                            COPYRIGHT
 *
 *  kbrace.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 Bracelets In Constant Amortized Time
 * Joe Sawada
 *
 */

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

int n, k;
int *a;

int check_rev(int t, int i)
{
  int j;
  for(j=i+1; j<=(t+1)/2; ++j){
    if(a[j] < a[t-j+1]) return(0);
    if(a[j] > a[t-j+1]) return(-1);}
  return(1);
}

void brace(int t, int p, int r, int u, int v, unsigned char rs)
{
  int rev, j;

  if(t-1 > (n-r)/2+r){
    if(a[t-1] > a[n-t+2+r]) rs = 0;
    else if(a[t-1] < a[n-t+2+r]) rs = 1;}

  if(t > n){
    if((rs == 0) && (n%p == 0)){
      for(t=1; t<n+1; ++t) printf("%d",a[t]);
      printf("\n");}}
  else{
    a[t]=a[t-p];
    v = a[t]==a[1] ? v+1 : 0;
    if((u == t-1) && (a[t-1] == a[1])) ++u;
    if((t == n) && (u != n) && (a[n] == a[1])){}
    else if(u == v){
      rev = check_rev(t, u);
      if(rev == 0) brace(t+1,p,r,u,v,rs);
      else if(rev == 1) brace(t+1,p,t,u,v,0);}
    else
      brace(t+1,p,r,u,v,rs);
    if(u==t) --u;
    for(j=a[t-p]+1; j<k; ++j){
      a[t]=j;
      if(t==1)
	brace(t+1,t,1,1,1,rs);
      else
	brace(t+1,t,r,u,0,rs);}}
}

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

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

  k = atoi(argv[1]);
  n = atoi(argv[2]);
  a = (int *)calloc(n+2,sizeof(int));
  brace(1,1,0,0,0,0);
  free(a);
  return(0);
}