Не могу проинициализировать массив (задача на комбинаторику)

Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий
Igor Makanu
9496
Igor Makanu  

Который час пытаюсь составить алгоритм инициализации массива по заданному примеру:

..................................

примерно такие должны получиться данные, массив трехмерный:

#define MAXARR  8

arr[][MAXARR][2]

принцип формирования данных.... что то примерно как....

первый элемент строки начинается с 1,1 (про нулевые значения не принципиально)

второй элемент строки может быть только или 0,0 или  0,1 или 1,0 или 0,2 или 2,0 или 1,2 или 2,1 или 2,2

третий элемент строки может быть ... не больше цифры 3, соответсвенно и 4-й элемент строки не может быть более значения 4 и т.д.

строки должны быть уникальными (без повторений)


в общем какая то задача на комбинаторику, но при всей свое простоте, почему то не получилось то что хотел

вот скрипт, который пытаю или испытываю:

#property strict

#define MAXARR  8

void OnStart()
  {
   int filehandle,i,j,k,l;
   string s;
   filehandle=FileOpen(StringConcatenate("InitArr.csv"),FILE_WRITE|FILE_CSV);
   if(filehandle!=INVALID_HANDLE)
     {
      Print("FileOpen OK");
      for(i=0;i<MAXARR;i++)
        {

         k=0;
         while(k<=i)
           {
            for(j=0;j<MAXARR;j++)
              {
               l=0;
               while(l<=MAXARR)
                 {
                  s+=StringConcatenate("{ ",l,",",k," } , ");
                  l++;
                 }
               FileWrite(filehandle,s);
               s="";
              }
            k++;

           }
        }
      FileClose(filehandle);
      Print("FileClose....");
     }
   else Print("Операция FileOpen неудачна, ошибка ",GetLastError());
  }
Maxim Kuznetsov
12900
Maxim Kuznetsov  
Igor Makanu:

Который час пытаюсь составить алгоритм инициализации массива по заданному примеру:

примерно такие должны получиться данные, массив трехмерный:

#define MAXARR  8

arr[][MAXARR][2]

принцип формирования данных.... что то примерно как....

первый элемент строки начинается с 1,1 (про нулевые значения не принципиально)

второй элемент строки может быть только или 0,0 или  0,1 или 1,0 или 0,2 или 2,0 или 1,2 или 2,1 или 2,2

третий элемент строки может быть ... не больше цифры 3, соответсвенно и 4-й элемент строки не может быть более значения 4 и т.д.

строки должны быть уникальными (без повторений)


в общем какая то задача на комбинаторику, но при всей свое простоте, почему то не получилось то что хотел

вот скрипт, который пытаю или испытываю:

hint - сумма 2-х цифр в каждом столбце = или 0  или номер столбца. Надо просто перебрать слагаемые и записывать переборы
Igor Makanu
9496
Igor Makanu  
Maxim Kuznetsov:
hint - сумма 2-х цифр в каждом столбце = или 0  или номер столбца. Надо просто перебрать слагаемые и записывать переборы

там не слагаемые, а сочетания из цифр

1,2,3,4,5,6,7,8

но для каждого столбца макс. число в столбце не более № столбца

гуглю уже все про комбинаторику, но где то уже "начал по кругу ходить" - не вижу очевидного 

очередная версия скрипта, но все не то...

#property strict

#define MAXARR  8

void OnStart()
  {
   int filehandle,i,j,k,l;
   string s;
   filehandle=FileOpen(StringConcatenate("InitArr.csv"),FILE_WRITE|FILE_CSV);
   if(filehandle!=INVALID_HANDLE)
     {
      Print("FileOpen OK");
      for(i=0;i<MAXARR;i++)
        {

         k=0;
         while(k<=i)
           {
            l=0;
            for(j=0;j<MAXARR;j++)
              {
               if(l<j)l++;
               s+=StringConcatenate("{ ",l,",",k," } , ");
              }
              FileWrite(filehandle,s);
              s="";
            k++;

           }
        }
      FileClose(filehandle);
      Print("FileClose....");
     }
   else Print("Операция FileOpen неудачна, ошибка ",GetLastError());
  }
Igor Makanu
9496
Igor Makanu  

нашел хороший пример http://cppalgo.blogspot.ru/2012/03/blog-post_20.html

void gen(int pos) {
  if (pos == n) {
    for (int i=0;i<n;++i)
      printf("%d",cur[i]);
    printf("\n");
    return;
  }
  for (int i=0;i<k;++i) {
    cur[pos] = i;
    gen(pos+1);
  }
}


но увы к своей задаче не получается применить, действительно дело в алфавите, а не только в переборе по циклам, алфавит у меня 1,2,3,4,5,6,7,8 , и все... не помню уже комбинаторику (((

Генерация всех размещений с повторениями рекурсивным способом
  • 2012.03.20
  • Игорь Беляев
  • cppalgo.blogspot.com.cy
Генерация такой последовательности не должно составить большого труда: Изначально функция gen запускается с параметром 0. Полное решение: здесь
Igor Makanu
9496
Igor Makanu  

если задачу решать в лоб, то примерно так:

//+------------------------------------------------------------------+
//|                                                      ProjectName |
//|                                      Copyright 2012, CompanyName |
//|                                       http://www.companyname.net |
//+------------------------------------------------------------------+
#property strict

#define MAXARR  8
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
   int filehandle;
   int arr[MAXARR][2];
   string s;

   filehandle=FileOpen(StringConcatenate("Arr.csv"),FILE_WRITE|FILE_CSV);
   if(filehandle!=INVALID_HANDLE)
     {
      for(int k=0;k<MAXARR;k++)
        {
         for(int z=0;z<MAXARR;z++)
           {
            for(int j=0;j<MAXARR;j++)
              {
               for(int i=0;i<MAXARR;i++)
                 {
                  s=StringConcatenate("{ ",k,",",z," }","{ ",z,",",k," }","{ ",z,",",j," }","{ ",j,",",z," }","{ ",z,",",i,"}","{",i,",",z," }",
                                      "{ ",i,",",j," }","{ ",j,",",i,"}");
                  FileWrite(filehandle,s);
                 }
              }
           }
        }
      FileClose(filehandle);
      Print("FileClose....");
     }
   else Print("Операция FileOpen неудачна, ошибка ",GetLastError());
  }
//----------------------------------------

но тут проблема, а если массив будет #define MAXARR  10 ? не будет работать

есть кто с программированием на ты?

Nikolai Semko
6567
Nikolai Semko  
Igor Makanu:

Который час пытаюсь составить алгоритм инициализации массива по заданному примеру:


#define MaxArr 8
#define MaxLin 100
void OnStart()
  {
   uint Arr[MaxLin][MaxArr][2];
   ArrayInitialize(Arr,1);
   for(int i=0;i<MaxLin;i++)
      for(int j=1;j<MaxArr;j++)
         while(Arr[i][j][0]==1 && Arr[i][j][1]==1)
           {
            Arr[i][j][0]=rand()%(j+2);
            Arr[i][j][1]=rand()%(j+2);
           }
   // распечатаем массив для проверки
   for(int i=0;i<MaxLin;i++)
     {
      string s="";
      for(int j=0;j<MaxArr;j++) s+=(string)Arr[i][j][0]+","+(string)Arr[i][j][1]+"  ";
      Print(s);
     }
Igor Makanu
9496
Igor Makanu  

О! Волшебники появились! Благодарю!

варюсь который час в собственном соку в интернете - голова уже звенит!

прям как глоток чистого воздуха! )))))

Nikolai Semko
6567
Nikolai Semko  
Igor Makanu:

О! Волшебники появились! Благодарю!

варюсь который час в собственном соку в интернете - голова уже звенит!

прям как глоток чистого воздуха! )))))

но проверки на уникальность каждой строки не осуществлялось.

Но для справки 

Число возможных комбинаций строки( при MaxArr =8 )  = 8*15*24*35*48*63*80 = 24 385 536 000

так что совпадения весьма маловероятны

А проверка на уникальность весьма ресурсная задача

Igor Makanu
9496
Igor Makanu  
Nikolai Semko:

но проверки на уникальность каждой строки не осуществлялось.

Но для справки 

Число возможных комбинаций строки( при MaxArr =8 )  = 8*15*24*35*48*63*80 = 24 385 536 000

Nikolai Semko:

неее, не совсем то, сейчас запустил скрипт в котором хочу сделать инициализацию массива, пишет что будет 2216 элементов, т.е. около 2000 элементов должно получиться при формировании массива инициализации, скрипт у меня считает ... сложно обьяснить, но считает в 2 прохода - сначала сформирует варианты пробоя Зигзага следующей вершиной, потом во втором проходе будет считать количество сколько раз на истории - не суть

но потом в экселе я вижу именно такую последовательность как выложил в первом посту, и проблема что в 2 прохода на ноутбуке считает на минутках очень долго, вот и хочу один проход убрать, минут наверное через 15 попробую файл экселя приатачить

именно в этом и проблема - в поиске уникальной последовательности - строки массива!


вот такие данные нужно получить - приатачил

Файлы:
array_8.zip 15 kb
Nikolai Semko
6567
Nikolai Semko  
Igor Makanu:
вот такие данные нужно получить - приатачил

Так в реальности какой размерности Вы будете использовать массив?

Если скажем в Вашем случае массив 2200X 8 X 2, то вероятность, что хотя бы две строки будут одинаковые примерно один шанс на  10 тысяч.

я просто задачи не понимаю. Этот массив необходимо сгенерировать один раз и скорость не имеет значения или скорость важна, т.к. он должен генерироваться постоянно?

Если Вам нужно сгенерировать массив только один раз и скорость не важна, то это элементарно -  проверить на уникальность каждую строку можно простым перебором. Займет пару секунд. 
Но если скорость важна, то придется чуть повозиться.

Но лично мне времени жаль, т.к. я осознаю слишком малую вероятность совпадения хотя бы одного совпадения. Это все равно что в лотерею выиграть.

Nikolai Semko
6567
Nikolai Semko  
Igor Makanu:

Nikolai Semko:

неее, не совсем то, сейчас запустил скрипт в котором хочу сделать инициализацию массива, пишет что будет 2216 элементов, т.е. около 2000 элементов должно получиться при формировании массива инициализации, скрипт у меня считает ... сложно обьяснить, но считает в 2 прохода - сначала сформирует варианты пробоя Зигзага следующей вершиной, потом во втором проходе будет считать количество сколько раз на истории - не суть

но потом в экселе я вижу именно такую последовательность как выложил в первом посту, и проблема что в 2 прохода на ноутбуке считает на минутках очень долго, вот и хочу один проход убрать, минут наверное через 15 попробую файл экселя приатачить

именно в этом и проблема - в поиске уникальной последовательности - строки массива!

:)))  Если это Вам нужно для индикатора на МТ, то забудьте про эксель. Это для школьных лабораторных работ.

MQL5 Вам дает все необходимое. Для проверки уникальности там всего то нужно 4 строчки кода добавить ( правда время выполнения вырастет на порядки). 
Если же Вы пытаете заниматься распознаванием образов и поисков патернов, то сразу скажу - не с той стороны зашли. 
Впрочем мне пора уходить. Семья зовет ))) Удачи.

123
Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий