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

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

Народ, может кто подкинет идею, как конструктивно сделать код, генерирующий все возможные комбинации какого-дибо набора символов.
:type:

Surround
Мало данных для анализа, как говоривает кое-кто из моих знакомых :)

И не говорите так: "конструктивно сделать код". Очень коряво звучит. Это относительно новое слово-паразит, "конструктивно". Ещё недавно было "концептуально". Перорально, млин.

hasherfrog
извиняюсь, я имел в виду, чтобы код был не грузный и не отнимал большое количество ресурсов на перебор
есть набор символов, скажем A и B. Нужно составить, например, все возможные 6-символьные комбинации из этих знаков, причем, чтобы ни одни подряд более 3х раз не повторялся.

hasherfrog

Цитата:

Цитата hasherfrog

Мало данных для анализа, как говоривает кое-кто из моих знакомых :)

Уж точно не я, данных вполне достаточно :)

Surround

Цитата:

Цитата Surround

есть набор символов, скажем A и B. Нужно составить, например, все возможные 6-символьные комбинации из этих знаков, причем, чтобы ни одни подряд более 3х раз не повторялся.

Заметьте, что это простейшая задача по двоичной арифметике, с ней возиться как минимум не интересно. Рассмотрите такой вариант:

Код:

program Project1; {by Savant}



{$APPTYPE CONSOLE}



uses

  SysUtils, Classes;



const

  js = 2; { Кол-во различных символов }

  jp = 3; { Максимально допустимое кол-во повторяющихся символов}

  jm = 6; { Кол-во символов в строке }

  a: array[1..js] of Char = ('A','B');

var

  i: Integer; { ИМХО byte/shortint не рекомендую использовать, при вычислениях он приводится к Cardinal/Integer }

  b: array[1..jm] of Char;

  res: TStrings;

function passed: Boolean;

{ Проверяет текущее значение b на допустимость по кол-ву повторений }

var

  x,y: Integer;

  c: array[1..jp+1] of Char;

begin

  Result:=True;

  for x:=1 to js do begin

    for y:=1 to jp+1 do c[y]:=a[x];

    if Pos(c,b) <> 0 then Result:=False;

  end;

end;

procedure moving(k,j: Integer);

var

  i: Integer;

begin

  for i:=j to js do begin

    b[k]:=a[i];

    if passed then

      if res.IndexOf(b)=-1 then res.Add(b);

    if k > 1 then moving(k-1,1);

  end;

end;

begin

  res:=TStringList.Create;

  try

    for i:=1 to jm do b[i]:=a[1];

    for i:=1 to jm do moving(i,2);

    for i:=0 to res.Count-1 do WriteLn(res.Strings[i]);

  finally

    res.Free;

  end;

  ReadLn;

end.

Как видите, он более универсальный. По умолчанию настроен на решение Вашей задачи. И вроде как даже работает :) . Вот что мне программа выдала после выполнения. Если результат неверен, предупреждайте сразу, я покопаюсь в коде:
BBBAAA
BABAAA
AABAAA
ABBAAA
BBABAA
BAABAA
AAABAA
ABABAA
BABBAA
AABBAA
ABBBAA
BBBABA
BBAABA
BAAABA
ABAABA
BABABA
AABABA
ABBABA
BBABBA
BAABBA
AAABBA
ABABBA
BABBBA
AABBBA
BBBAAB
BBAAAB
ABAAAB
BABAAB
AABAAB
ABBAAB
BBABAB
BAABAB
AAABAB
ABABAB
BABBAB
AABBAB
ABBBAB
BBBABB
BBAABB
BAAABB
ABAABB
BABABB
AABABB
ABBABB
BBABBB
BAABBB
AAABBB
ABABBB

p.s.: я тут несколько по геморному скопировал код, если чо не компилится, сообщайте.

Savant
>> Уж точно не я, данных вполне достаточно
Ну-ну :) Условие "что бы каждый символ не повторялся бы более 3-х раз" Вы, очевидно, прочитали в голове Surround с помощью телепатии?

И решение, похоже, неверное. Вариант решения (уже 2, 3-й по порядку) - не удовлетворяет вышеупомянутому условию.

hasherfrog
Не повторялся бы подряд более трёх раз!

Savant
Да, действительно :) Ну что ж, поздравляю с победой :)

hasherfrog

Победой в чём? Подожди поздравлять, вот когда явится Surround, посмотрит на всё ЭТО, и не скажет "полный отстой", тогда можешь поздравить :)

Кстати, задачи, где речь идёт о комбинациях из 2-х символов. можно решать и по-другому :)

Нетрудно заметить, что общее количество комбинаций в данном случае (без дополнительного условия о 3-х) описывается двоичными числами от 0 до 2**6, т.е. символ==бит. И остается только проверить все числа от 0 до 63 на это самое условие...

:)

hasherfrog

Цитата:

Кстати, задачи, где речь идёт о комбинациях из 2-х символов. можно решать и по-другому

Нетрудно заметить, что общее количество комбинаций в данном случае (без дополнительного условия о 3-х) описывается двоичными числами от 0 до 2**6, т.е. символ==бит. И остается только проверить все числа от 0 до 63 на это самое условие...

Я это знаю, поэтому специально перед своей прогой сделал небольшой заголовок:

Цитата:

Цитата Savant

Заметьте, что это простейшая задача по двоичной арифметике, с ней возиться как минимум не интересно.

Ух нафлудили.... :)

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

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;

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

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

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

Код:

/* 

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

}

Вчера просмотрел свой код и понял, что очень СИЛЬНО проглючил и неэффективно решил задачу.
Хотя функция 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);        

}