*Решено* | Задача по комбинаторике. Генератор комбинаций

Surround · Отправлено: **08:11, 16-01-2005** | #11

только чего-то не могу понять, по какому принципу заполняется массив b с символами...

Savant · Отправлено: **12:30, 16-01-2005** | #12

Surround

Цитата:

по какому принципу заполняется массив b с символами?

Лично мне вспомнили старые кассовые аппараты (или что-то типа того). Ну короче. Представь бесконечно длинный стержень. На нём jm колец, на каждом из которых высечено js символов. Изначально на всех кольцах стоит первый символ. И дальше они слева направо начинают крутиться

. Дальше объяснения перейдут непосредственно к коду, иначе не понять всех тонкостей

.

Код:

procedure moving(k,j: Integer);
{ рекурсивная функция, сдвигает символ в k-той позиции, начиная с j-ного }
var
  i: Integer; { "счетчик" цикла }
begin
  for i:=j to js do begin { т.к. придется прокрутить ВСЕ символы, ставим цикл}
    b[k]:=a[i]; { прокручиваем на 1 символ вперед в текущей k-той позиции }
    if passed then { проверяем получившуюся строку b на соответствие условию }
      if res.IndexOf(b)=-1 then res.Add(b); { добавляем в общий список, если такого там еще нет }
{ Здесь я обязан сделать отступление и прокомментировать предыдущую строчку:
   не знаю по каким причинам, но примерно 10% результатов повторяются =) , кто найдет
   место "облома", тому огромная благодарность }
    if k > 1 then moving(k-1,1); { если есть еще кольца слева, то крутим и их }
{ Заметьте, что здесь j=1, а при вызове из главной программы j=2,
   это введено для уменьшения цикла, т.к. изначально на всех кольцах 
   установлен первый символ из списка, т.е. b[k] уже равно a[1] }
  end;
end;

Ну хоть немножко я прояснил ситуацию?

Surround · Отправлено: **07:55, 18-01-2005** | #13

немного есть...

mrcnn · Отправлено: **21:05, 16-02-2005** | #14

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

Код:

/* 
 * 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);				
}

mrcnn · Отправлено: **02:16, 18-02-2005** | #15

Вчера просмотрел свой код и понял, что очень СИЛЬНО проглючил и неэффективно решил задачу.
Хотя функция recursivetransposition была написана корректно, но применить ее надо было к изначально заданному массиву.

Код:

#include <stdio.h>

#define N 2
#define MAX 10
#define SIZE 10


int recursivetransposition(char k[],char temp[],int index); 
void print (char temp[]);                     /*Распечатка*/
int ismatch(char temp[]);
int isall(char k[], char temp[]);

void main(){
	char temp[SIZE];
	char k[N]={'m','a'}; /*Заданный массив*/
	recursivetransposition(k, temp, 0);
}

int recursivetransposition(char k[],char temp[],int index){
	int i;
	for (i = 0; i < N; i++){
			temp[index] = k[i];
			if ( index == SIZE-1 )
			{			
				if (ismatch(temp))
					if(isall(temp,k))
						print(temp);
			}			
			else {
				index++;
				index=recursivetransposition(k, temp, index);/**/				
			}
		}
	
	index--;
	return(index);
	}

void print (char temp[]){
	int j;
	for (j=0; j<SIZE; j++)
		{
		printf ("%c", temp[j]);
		}
	printf ("\n");

}

int ismatch(char temp[]){
	int j;
	int test=0;
	for(j=1; j<SIZE;j++)
		if (temp[j] != temp[j-1])
			test=0;
		else
		{
			test++;
			if (test>=MAX)
				return(0);
		}
		return(1);
		}


int isall(char k[], char temp[]){
	int i,j,est;
	for(i=0;i<N;i++){
		for(est=0, j=0;j<SIZE;j++){
			if(temp[i]==k[j])
				est=1;
		}
		if (est==0)
			return(0);
		}
	return(1);	
}