Пятница, 29 Марта 2024, 08:54

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
Форум игроделов » Движки для разработки игр и сложные системы разработки » Unity » Комбинаторика
Комбинаторика
EzKekPoliceДата: Четверг, 22 Декабря 2016, 16:34 | Сообщение # 1
частый гость
Сейчас нет на сайте
Привет всем, может кто подсказать алгоритм, как найти все возможные комбинации работающий примерно так

abc - алфавит

abc
acb
bca
bac
cba
cab
ab
ba
ac
ca
bc
cb
a
c
b

Надеюсь понятна моя мысль
falcowareДата: Четверг, 22 Декабря 2016, 18:03 | Сообщение # 2
старожил
Сейчас нет на сайте
for(ix = 0; ix < 3; ix++){
for(iy = 0; ix < 3; iy++){
for(iz = 0; iz < 3; iz++){

if(ix == iy){ continue; }
if(ix == iz){ continue; }
if(iy == iz){ continue; }

тут все комбинации порядковых номеров. от нуля до 3. А дальше думаю идею поняли! =)

}
}
}
ReanДата: Четверг, 22 Декабря 2016, 23:48 | Сообщение # 3
участник
Сейчас нет на сайте
falcoware, blink
EzKekPolice, если чисто с точки зрения комбинаторики, то это получается сумма размещений с последовательным уменьшением количества элементов слова. Для алфавита с мощностью 3, выглядит так:



где количество размещений



Реализация данного алгоритма на языке C#:
Рекурсивные методы:

С использованием циклов:


Сообщение отредактировал Rean - Четверг, 22 Декабря 2016, 23:54
falcowareДата: Четверг, 22 Декабря 2016, 23:53 | Сообщение # 4
старожил
Сейчас нет на сайте
Rean, я так понял, не число нужно, а именно сами значения, то есть выражения. Число комбинаций найти не трудно.
ReanДата: Четверг, 22 Декабря 2016, 23:55 | Сообщение # 5
участник
Сейчас нет на сайте
falcoware, в таком случае согласен, не так понял.
8Observer8Дата: Суббота, 24 Декабря 2016, 13:08 | Сообщение # 6
заслуженный участник
Сейчас нет на сайте
EzKekPolice, у вас алфавит состоит из трёх букв или вы для примера привели и может быть произвольное количество букв?
falcowareДата: Суббота, 24 Декабря 2016, 13:23 | Сообщение # 7
старожил
Сейчас нет на сайте
8Observer8, очевидно, нужно общее решение. Задача нетривиальная.
8Observer8Дата: Суббота, 24 Декабря 2016, 14:38 | Сообщение # 8
заслуженный участник
Сейчас нет на сайте
falcoware, я просто смотрю у вас циклы от 0 до 3, меня это смутило. А если нужно до произвольного n? В общем, не понял вашу идею.

Сообщение отредактировал 8Observer8 - Суббота, 24 Декабря 2016, 14:39
falcowareДата: Суббота, 24 Декабря 2016, 14:45 | Сообщение # 9
старожил
Сейчас нет на сайте
8Observer8,

как Вам структура:

void MyFor(int n, int ncycle){

if(n ==0){ return; }
for(int ix = 0; ix < ncycle; ix++){
MyFor(n - 1, ncycle);
}
}

Для произвольных n циклов?


Сообщение отредактировал falcoware - Суббота, 24 Декабря 2016, 14:47
8Observer8Дата: Суббота, 24 Декабря 2016, 15:16 | Сообщение # 10
заслуженный участник
Сейчас нет на сайте
Цитата falcoware ()
тут все комбинации порядковых номеров. от нуля до 3. А дальше думаю идею поняли!

Я про это. Не понял идею.
falcowareДата: Суббота, 24 Декабря 2016, 15:27 | Сообщение # 11
старожил
Сейчас нет на сайте
8Observer8,

char arr[] = "abc";

for(ix = 0; ix < 3; ix++){
for(iy = 0; ix < 3; iy++){

CString sStringResult;
for(iz = 0; iz < 3; iz++){

if(ix == iy){ continue; }
if(ix == iz){ continue; }
if(iy == iz){ continue; }

// тут все комбинации порядковых номеров. от нуля до 3. А дальше думаю идею поняли! =)

sStringResult = CString(arr[ix]) + CString(arr[iy]) + CString(arr[iz]);

}
}
}

Что тут сложного?
8Observer8Дата: Суббота, 24 Декабря 2016, 16:30 | Сообщение # 12
заслуженный участник
Сейчас нет на сайте
Цитата falcoware ()
Что тут сложного?

Вот этот комментарий "тут все комбинации порядковых номеров. от нуля до 3" (точнее, будущий код под ним и что там должно быть?) как влияет на результат sStringResult?


Сообщение отредактировал 8Observer8 - Суббота, 24 Декабря 2016, 16:31
falcowareДата: Суббота, 24 Декабря 2016, 16:48 | Сообщение # 13
старожил
Сейчас нет на сайте
8Observer8,

ну мы разложили тройной алфавит.
Двойной очевидно будет так:

char arr[] = "abc";

for(ix = 0; ix < 3; ix++){
for(iy = 0; ix < 3; iy++){

CString sStringResult;
for(iz = 0; iz < 3; iz++){

if(ix == iy){ continue; }
if(ix == iz){ continue; }
if(iy == iz){ continue; }

// тут все комбинации порядковых номеров. от нуля до 3. А дальше думаю идею поняли! =)

sStringResult = CString(arr[iy]) + CString(arr[iz]);

}
}
}
ReanДата: Суббота, 24 Декабря 2016, 19:48 | Сообщение # 14
участник
Сейчас нет на сайте
Вот рабочий масштабируемый вариант. Представляет из себя работу с функцией по нахождению всех комбинаций размещения множества n (src) по k элементам.


Из минусов: string'и и рекурсия. Зато достаточно компактно.
Ссылка на реализацию: Permutation


Сообщение отредактировал Rean - Воскресенье, 25 Декабря 2016, 02:22
8Observer8Дата: Суббота, 24 Декабря 2016, 20:13 | Сообщение # 15
заслуженный участник
Сейчас нет на сайте
falcoware, хорошо, для тройного + двойной + одинарный алфавитов - ваш подход работает. Напишите, пожалуйста, подробнее, как быть со строками произвольной длины.

Вот что сейчас выдаёт программа:
abc
bc
acb
cb
bac
ac
bca
ca
cab
ab
cba
ba
a
b
c



Добавлено (24 декабря 2016, 20:13)
---------------------------------------------
Rean, отличная работа! Маленькое замечание. У меня VS ругнулся на строку "if (!lStr.Contains(ch))", что не может преобразовать "char" в "string", я добавил преобразование в строку "if (!lStr.Contains(ch.ToString()))"


Сообщение отредактировал 8Observer8 - Суббота, 24 Декабря 2016, 20:14
falcowareДата: Суббота, 24 Декабря 2016, 20:21 | Сообщение # 16
старожил
Сейчас нет на сайте
8Observer8, ну очевидно нужно переписать цикл на динамический:

Код


int arrFors[] = {1,2,3,4,5,6,7...};

void MyFor(int n, int nIndex){

if(nIndex == 1){ return; }

for(int ix = 0; ix < n; ix++){
  if(ix == arrFors[nIndex]){ continue; }
    MyFor(n, nIndex - 1);

    for(jx = 0; jx < n; jx++){
       CString ResultString;
       for(kx = jx; kx < n; kx++){
         ResultString += CString(arr[kx]);
      }
    }    
}
}


Как то так. =)
ReanДата: Воскресенье, 25 Декабря 2016, 02:06 | Сообщение # 17
участник
Сейчас нет на сайте
8Observer8, спасибо!

Цитата 8Observer8 ()
Маленькое замечание. У меня VS ругнулся на строку "if (!lStr.Contains(ch))", что не может преобразовать "char" в "string", я добавил преобразование в строку "if (!lStr.Contains(ch.ToString()))"

Странно. У меня в VS 2015 есть перегрузка с char. Но можно и через ToString() (думаю, там так и реализовано) :)

Добавлено (25 декабря 2016, 02:06)
---------------------------------------------
Глянул на подключенные пространства: так у меня там Linq, оттуда и перегрузка с char ;)
А вот здесь можно рассмотреть/обсудить C++ версию от falcoware. Я сильно не вдавался в подробности, что и как работает. Если у кого будет желания - можете допилить.

Сообщение отредактировал Rean - Суббота, 24 Декабря 2016, 22:39
falcowareДата: Воскресенье, 25 Декабря 2016, 05:26 | Сообщение # 18
старожил
Сейчас нет на сайте
Rean, ладно, твое КунгФу круче, сдаюсь! :D
8Observer8Дата: Воскресенье, 25 Декабря 2016, 10:01 | Сообщение # 19
заслуженный участник
Сейчас нет на сайте
У меня мелькнула мысль, что до нас эту задачу решали. Выяснил, что у Кнут'а есть 4-й том разбитый на части:
Искусство программирования, том 4А. Комбинаторные алгоритмы , часть 1
Искусство программирования, том 4, выпуск 2. Генерация всех кортежей и перестановок
Искусство программирования, том 4, выпуск 3. Генерация всех сочетаний и разбиений

Если для автора темы всё ещё актуальна эта проблема, то возможно в книге он найдёт что-то полезное для себя.
Форум игроделов » Движки для разработки игр и сложные системы разработки » Unity » Комбинаторика
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг