[mrcnn]

Случайно вчера наткнулся на этот топик.
Задача показалась мне интересной, и я даже постарался рассмотреть самый общий случай.
Исходник на Си.

Код:

/* 
 * perestanovka.c
 * (c) 2005, mrcnn 
 *
 * Программа, выводящая на терминал все перестановки 
 * NUM элементов из опр. массива таким образом, чтобы каждый элемент 
 * не повторялся подряд более чем MAX раз в составленной комбинации длины LENGTH
 *
 * Идея алгоритма:
 * 1. Составить перестановки  с повторениями чисел меньше MAX  таким образом, 
 *    чтобы в сумме они составляли LENGTH
 * 2. Составить возможные комбинации употребления символов из заданного массива
 *    в соответствии с цифрами опр. на шаге 1 (для каждого размещения) 
 * 3. Распечатка результатов
*/ 

#include <stdio.h>	 /* printf */
#include <windows.h> /* CharToOem */

#define NUM 2	/* можно изменять:  NUM >= 2 */
#define MAX 3	/* можно изменять:  MAX >= 1 */ 
#define LENGTH 6	/* можно изменять:  LENGTH >= 1*/

char k[NUM]={'а','в'}; 
/* вместе с изменением NUM  следует добавить в/убрать из массива k[NUM] элементы, 
соответствующие/не соответствующие новому размеру*/ 

#pragma auto_inline (on)
int recursivetransposition(int digits[],int temp[], int index,int size);
#pragma auto_inline (on)
int recursivetransposition2(char dest[],int temp[], char t[],int index, int size);
#pragma auto_inline (on)
void print (int temp[], int size); 
#pragma auto_inline (on)
void transposition(char k[]);
#pragma auto_inline (on)
int test(char dest[],char t[],int size);

void main(){	
  int temp[LENGTH];
  int digits[MAX];
  register int i,j, index = 0;

  /* заполнение массива digits цифрами от 1 до MAX-1 в возрастающем порядке */
  for (i = 0, j = 1; i < MAX; i++,j++)
      digits[i]=j;

  for ( i = 1; i <= LENGTH;i++, index = 0)	
      recursivetransposition(digits, temp, index, i);
}

/* реализация перестановок с повторениями */
int recursivetransposition(int digits[],int temp[],int index, int size){
  register int i;
  for (i = 0; i < MAX; i++){
      temp[index] = digits[i];
      if ( index == size-1 )
      {
            print (temp,size);
      }
      else 
      {
            index++;
            index=recursivetransposition(digits, temp, index,size);/**/            
       }
  }
   
   index--;
   return(index);
}

/* реализация перестановок с повторениями c вычетом тех перестановок 
где элементы повторяются подряд 2 раза */
int recursivetransposition2(char dest[],int temp[], char t[], int index, int size){
    register int i,j,n,m;
    for (i = 0; i < NUM; i++){
        if(index != 0)			
            if (t[index-1]!=dest[i])
                 t[index] = dest[i];
            else
                 continue;
        else
            t[index] = dest[i];			
			
    if ( index == size-1)
    {
        if (test(dest,t,size)){
        for(j=0,n=0;j<size;j++,n++)
             for (m=temp[n];m>0;m--)
                  printf("%c", t[j]);
             printf("\n");
          }
    }
    else 
    {
         index++;
         index=recursivetransposition2(dest, temp, t, index,size);/**/
    }
    }	
    index--;
    return(index);
}

void print (int temp[], int size)
{
    register int i,j,n,sum=0;	
    char t[LENGTH];
    char dest[NUM];/* для CharToOem  */	
    for (j=0; j<size; j++)
        sum+=temp[j];
    if (sum==LENGTH)
        {
        if (NUM==2)
            {	
            CharToOem(k,dest);
            for (i=0;i<NUM;i++)
                  {
                  for (j=0; j<size;j++)
                         if (j%2==0)
                               for (n=temp[j]; n>0; n--)
                                      printf ("%c", dest[0]);
                         else
                               for (n=temp[j]; n>0; n--)
                                      printf ("%c", dest[1]);
                  printf ("\n");			
                  transposition(dest);
                  }
            }
            else if (NUM>=3){
                   CharToOem(k,dest); 
                   recursivetransposition2(dest,temp,t,0, size);
                  }		
           /*Инфа для справки*//*
           for (j=0; j<size; j++)
          {
               printf ("%d", temp[j]);
          }
          printf ("\n");/**/
    }
}

void transposition(char k[])
{
    register char tmp;
    tmp=k[NUM-2];
    k[NUM-2]=k[NUM-1];
    k[NUM-1]=tmp;
}

/* проверка все ли элементы массива dest  входят в массив t 
Для того чтобы при N >= 3 в список выводимых перестановок не были включены те,
куда не входит каждый элемент из массива k */
int test(char dest[], char t[],int size){
    register int i,j,est;
    for(i=0;i<NUM;i++){
        for(est=0, j=0;j<size;j++){
            if(dest[i]==t[j])
                est=1;
           }
        if (est==0)
        return(0);
        }
    return(1);				
}