#include <stdio.h>

#define MAXSIZE 100

int ncp;

int printArr ( int A[] , int s )
{
   int i,c=0;

   c += printf("{");
   if (s > 0) {
      for (i=0; i<=s-2; ++i) c += printf("%d,",A[i]);
      c += printf("%d",A[s-1]);
   }
   c += printf("} ");
   return(c);
}

int printLinGrps ( int n , int A[] , int s )
{
   int i,m,M,cnt;

   if (ncp+3*s >= 79) { printf("\n"); ncp = 0; }
   ncp += printArr(A,s);
   cnt = 1;
   m = (s == 0) ? 1 : A[s-1]+2;
   M = n;
   for (i=m; i<=M; ++i) {
      A[s] = i;
      cnt += printLinGrps(n,A,s+1);
   }
   return cnt;
}

int printCirGrps ( int n , int A[] , int s )
{
   int i,m,M,cnt;

   if (ncp+3*s >= 79) { printf("\n"); ncp = 0; }
   ncp += printArr(A,s);
   cnt = 1;
   if (s == 0) {
      m = 1;
      M = n;
   } else {
      m = A[s-1] + 2;
      M = (A[0] == 1) ? n-1 : n;
   }
   for (i=m; i<=M; ++i) {
      A[s] = i;
      cnt += printCirGrps(n,A,s+1);
   }
   return cnt;
}

int main ()
{
   int i, n, A[MAXSIZE], cnt;

   printf("How many people? "); scanf("%d",&n);
   for (i=0; i<80; ++i) printf("*"); printf("\n"); ncp = 0;
   printf("Nonbelligerent collections on a line:\n");
   cnt = printLinGrps(n,A,0);
   printf("\nTotal count = %d\n", cnt);
   for (i=0; i<80; ++i) printf("*"); printf("\n"); ncp = 0;
   printf("Nonbelligerent collections on a circle:\n");
   cnt = printCirGrps(n,A,0);
   printf("\nTotal count = %d\n", cnt);
   for (i=0; i<80; ++i) printf("*"); printf("\n");
}