Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5 6 7 8 9   вперед  Ctrl      все
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
Мудроглюков
Gennadiy Usov
Большая просьба!
Не подскажите, где можно найти алгоритм поиска всех возможных сочетаний из К чисел, включая одно число.
Хотя с одним числом все ясно.
Данный алгоритм необходим для поиска сочетаний двоек вертикалей при определения решений на досках МхМ.
В дальнейшем необходимо будет ввести ограничения, например, цифра 4 не может быть с цифрой 7 в одном сочетании.


это обычно называют комбинаторной генерацией с, тоже обычным, отсечением неподходящих
вариантов на разных шагах генерации очередного варианта

Задачу повнятнее опиши, если нужны советы: матрица заполняется числами с повторением и
и какие конфигурации чисел годны и что нужно оценивать и в каких критериях на
пригодных конфигурациях?

Имеется несколько последовательностей чисел: 1,2,3, далее 1,2,3,4,5,6, далее 1,2,3,4,5,6,7,8,9, и т.д.
Для каждой нужно найти все сочетания. При этом:
В первой последовательности в одном сочетании не могут быть 1 и 2, во второй - 1 и 3, 2 и 4, 3 и 5, 4 и 6,
в третьей - 1 и 4, 2 и 5, 3 и 6, 4 и 7, 5 и 8, 6 и 9 и т.д.
Здесь видно, что существует некоторая прогрессия, которую можно распространить на последовательность, длиной 3 х К.
Вот и все.
24 мар 18, 15:24    [21283022]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13868
Gennadiy Usov
С другой стороны получился неплохой алгоритм поиска сочетаний21282517. Удобный, и цикл только один: от 1 до N.
Чем этот алгоритм не нравится?

Если подошел, то пользуйся. Мне показалось там совсем про другую задачу.
24 мар 18, 15:25    [21283023]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8315
Gennadiy Usov
Мудроглюков
пропущено...


это обычно называют комбинаторной генерацией с, тоже обычным, отсечением неподходящих
вариантов на разных шагах генерации очередного варианта

Задачу повнятнее опиши, если нужны советы: матрица заполняется числами с повторением и
и какие конфигурации чисел годны и что нужно оценивать и в каких критериях на
пригодных конфигурациях?

Имеется несколько последовательностей чисел: 1,2,3, далее 1,2,3,4,5,6, далее 1,2,3,4,5,6,7,8,9, и т.д.
Для каждой нужно найти все сочетания. При этом:
В первой последовательности в одном сочетании не могут быть 1 и 2, во второй - 1 и 3, 2 и 4, 3 и 5, 4 и 6,
в третьей - 1 и 4, 2 и 5, 3 и 6, 4 и 7, 5 и 8, 6 и 9 и т.д.
Здесь видно, что существует некоторая прогрессия, которую можно распространить на последовательность, длиной 3 х К.
Вот и все.


в таком контексте наверно не последовательности (математические), а наборы из чисел из ... от 1 до 99 ...
и сочетания же: из множества М по сколько и с повторениями ли?
24 мар 18, 16:16    [21283046]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41465
Треугольник Паскаля нам тут в помощь?
24 мар 18, 17:00    [21283073]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1748
Gennadiy Usov,

Перебор перестановок, размещений, сочетаний http://www.guildalfa.ru/alsha/node/26
24 мар 18, 18:44    [21283210]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
Мне предложили несколько вариантов алгоритмов определения сочетаний, так что глаза разбегаются. Буду изучать эти алгоритмы и сравнивать.
А пока попробую составить свой алгоритм, ведь остальные создают свои алгоритмы, о котором говорил в сообщении21282517.

Допустим, что есть последовательность чисел от 1 до М1.
Массив С (М1) предназначен для хранения одного сочетания.
Необходимо найти все сочетания этих чисел.

A = i, 1 <= i <= B, B = (2 в степени М1) – 1, А - переменная.

Переводим А в двоичный вид и каждую цифру двоичного вида числа А (0 или 1) помещаем в элементы массива С (М):
j = 1,
С( 1 ) = остаток от деления (А / 2), D = А / 2, D – переменная,
метка 1:
если мы хотим иметь в массиве С не единицы, а конкретные цифры, то С ( j ) = j,
если D = 0 то (массив С (М) сформирован, М = j, ищем новое значение А – переходим на метку 2).
j = j +1, С ( j ) = остаток от деления (С ( j - 1 ) / 2), D = С ( j - 1 ) / 2, возврат на метку 1.

метка 2:
Теперь можно для запоминания сочетания поместить его в двумерный массив:
С1 (I, j ) = С ( j ), 1 <= j <= М, С1 (В, М1 ) и
остальные ячейки строки заполнить нулями:С1 (I, j ) = 0, М < j <= М1,

Получается, что массив сочетаний состоит либо из 0 и 1, либо из 0 и конкретных цифр. Можно добавить процедуру, если нужно, которая убирает нули.
Вот и все сочетания.
25 мар 18, 06:53    [21283691]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
Алгоритм 21283691 позволяет частично решить задачу 21283022.
В задаче В чисел, причем В кратно 3. Разделим эти числа на три части, А = В/3, в первой части первые А чисел, во второй - средние А чисел, в третьей - последние А чисел.
Для первых А чисел количество сочетаний будет равно В1, где В1= 2 в степени А. Эти сочетания будут соответствовать числа от 0 до (В1 - 1). Здесь 0 необходим, поскольку будут циклы.
Теперь можно найти сочетания для чисел, которые составляют 1-ую и 3-ю части.
Для этой цели формируем массив В2 (В3), где В3 = В1 х В1.
Тогда В2 (i x В1 + j) = i x В3 + j, 0 <= i <= В1, 0 <= j <= В1.
Чтобы определить сочетания, надо элементы массива В2 (В3) разложить на составляющие согласно алгоритму 21283691
26 мар 18, 16:52    [21287095]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
unregestered
Member

Откуда:
Сообщений: 397
https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

Не забудьте проверить лицензии прежде чем чо-то включать
26 мар 18, 17:40    [21287301]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
unregestered
https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

Не забудьте проверить лицензии прежде чем чо-то включать

Это к чему?
26 мар 18, 19:30    [21287635]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
unregestered
Member

Откуда:
Сообщений: 397
что к чему?
27 мар 18, 01:39    [21288254]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
unregestered
https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

Не забудьте проверить лицензии прежде чем чо-то включать

при чем здесь лицензии, или просто что-то надо сказать, типа, скучно
27 мар 18, 05:48    [21288288]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
Gennadiy Usov
В задаче В чисел, причем В кратно 3. Разделим эти числа на три части, А = В/3,


Может оказаться, что при достаточно больших значений В, например, для доски 1000х1000 это значение более 20, количество сочетаний может превышать размер ячейки на компьютере. Поэтому лучше использовать массивы сочетаний более мелких массивов, а уже их них составлять большие массивы способом, аналогичным алгоритму 21283691.
27 мар 18, 07:28    [21288326]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Мудроглюков
Member

Откуда:
Сообщений: 8315
unregestered
https://google.github.io/guava/releases/snapshot-jre/api/docs/index.html
https://github.com/dpaukov/combinatoricslib

Не забудьте проверить лицензии прежде чем чо-то включать


А какие алгоритмы-то использовал автор?
Или чт автор считает, что он что-то оригинальное реализовал,
хотя может быть, что ОРИГИНАЛЬНОЕ - тогда тем более заявить-описать "в чем и что оригинальное?"?

_______
Вот ПЕРЕСТАНОВКИ - уже выделяют ЧЕТЫРЕ типа алгоритмов:
- лексикографическое упорядочение
- вестор инверсий
- транспозиции смежных элементов
- вложенные циклы
ЗЫ и для разных задач - разные типы по-разному пригодны оказываются (при углублении в тему открываются всякая всячина)
ЗЫ 5-ый тип может быть уже кем-то изобретен.
27 мар 18, 07:51    [21288376]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
Александр Бердышев
Если сочетаний n, то 2^n - 1

0001
0010
0011
0100
0101
0110
0111
1111
1001
1010
1011
1100
1101
1110
1111

Строишь такую матрицу из 0 и 1.
Потом цикл от i = 1 до n
i - строка.
Где единицы - берёшь символ, где 0 - не берёшь символ.

Есть еще вариант представления сочетаний с использованием этой ЗАМЕЧАТЕЛЬНОЙ картинки:
На картинке 15 сочетаний. Добавляем к ним вначале 16-е сочетание - 0000.
Пусть эти сочетания находятся в матрице большого размера, и сочетания в этой матрице имеют координаты: колонки (1,2,3,4) и строчки (1,2,...16).
Тогда матрица 4х16 копируется и добавляется к начальной матрице. Получаем матрицу 4х32.
Теперь добавляем к добавленной матрице 5-ю колонку с 1, и новая добавленная матрица и начальная матрица образуют матрицу 5х32 ( у начальной матрице в 5-й колонке будут 0).
В результате получили сочетания для пяти чисел!
Аналогично можно будет построить сочетания для любых чисел, если позволяет компьютер (размер матрицы!).
Сочетание 0000 используется только для построения матриц, при использовании матриц в расчетах это сочетание не нужно.
29 мар 18, 07:22    [21294829]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
Теперь появилась новая задачка:
Имеется несколько последовательностей чисел: 1,2,3, далее 1,2,3,4,5, далее 1,2,3,4,5,6,7, и т.д.
Для каждой последовательности чисел нужно найти все сочетания. При этом:
в первой последовательности в одном сочетании не могут быть 1 и 3,
во второй - 1 и 4, 2 и 5,
в третьей - 1 и 5, 2 и 6, 3 и 7, и т.д.
Здесь видно, что существует некоторая прогрессия, которую можно распространить на последовательность чисел, длиной 1 + 2 х К.
29 мар 18, 08:01    [21294859]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 68
Gennadiy Usov,

С такими ограничениями проще всего сделать рекурсивную генерацию - на следующий уровень рекурсии передаем текущий набор (не стоит называть их сочетаниями - всё-таки сочетание есть устоявшийся термин из комбинаторики) и модифицированную маску ограничения

   procedure GenLimitedSets(NMax, ASet, CurIdx, Mask, LimGap: integer);
   var
     tm: Integer;
   begin
     if CurIdx = NMax then
        Memo1.Lines.Add(BinS(ASet, NMax))  //бинарное представление числа
     else begin
        GenLimitedSets(NMax, ASet, CurIdx + 1, Mask, LimGap);
        tm := 1 shl (CurIdx + 1);
        if (Mask and tm) = 0 then
           GenLimitedSets(NMax, ASet or tm, CurIdx + 1, Mask or (tm shl LimGap), LimGap);
     end;

   end;

  GenLimitedSets(6, 0, 0, 0, 2);

000000
100000
010000
110000
001000
011000
000100
100100
001100
000010
100010
010010
110010
000110
100110
000001
100001
010001
110001
001001
011001
000011
100011
010011
110011
29 мар 18, 08:56    [21294937]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 68
Вот для примера 5/3 (1,2,3,4,5, не могут быть 1 и 4, 2 и 5)
00000
10000
01000
11000
00100
10100
01100
11100
00010
01010
00110
01110
00001
10001
00101
10101
00011
00111
29 мар 18, 09:03    [21294958]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
MBo
Вот для примера 5/3 (1,2,3,4,5, не могут быть 1 и 4, 2 и 5)
00000
10000
01000
11000
00100
10100
01100
11100
00010
01010
00110
01110
00001
10001
00101
10101
00011
00111

Когда рассматриваешь массивы очень большие, необходимо иметь программное обеспечение для поиска сочетаний. Ручной способ здесь не помогает
29 мар 18, 10:13    [21295187]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
MBo
Gennadiy Usov,

С такими ограничениями проще всего сделать рекурсивную генерацию - на следующий уровень рекурсии передаем текущий набор (не стоит называть их сочетаниями - всё-таки сочетание есть устоявшийся термин из комбинаторики) и модифицированную маску ограничения


А если количество цифр 250? Можно будет определить все сочетания?
29 мар 18, 10:35    [21295278]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 68
Gennadiy Usov,

автор
А если количество цифр 250? Можно будет определить все сочетания?


2^250 множеств нереально перебрать, и тем более обработать и вывести или записать.
С ограничениями их будет поменьше, но даже 2^64 уже непомерно много (понадобится 600 лет при генерации миллиарда множеств в секунду)
29 мар 18, 10:47    [21295322]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
MBo
Gennadiy Usov,

автор
А если количество цифр 250? Можно будет определить все сочетания?


2^250 множеств нереально перебрать, и тем более обработать и вывести или записать.
С ограничениями их будет поменьше, но даже 2^64 уже непомерно много (понадобится 600 лет при генерации миллиарда множеств в секунду)

1. А сколько будет немного? И как быть с величиной ячейки?
2. А как же англичане, которые считают на доске 1000х1000 и зависают (почему-то), хотя там намного больше решений20960899?
3. А помечтать, что компьютер будет когда-то быстрее?
29 мар 18, 11:17    [21295450]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 68
Gennadiy Usov,

>1. А сколько будет немного? И как быть с величиной ячейки?

Если перебирать все варианты, то считабельно 2^32-2^42 (10^14). Про ячейки я не в курсе.

>2. А как же англичане, которые считают на доске 1000х1000 и зависают (почему-то), хотя там намного больше решений20960899?

Вероятно, они используют алгоритм, не требующий брутфорсного перебора
29 мар 18, 11:29    [21295487]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
MBo
Gennadiy Usov,

>1. А сколько будет немного? И как быть с величиной ячейки?

Если перебирать все варианты, то считабельно 2^32-2^42 (10^14). Про ячейки я не в курсе.

>2. А как же англичане, которые считают на доске 1000х1000 и зависают (почему-то), хотя там намного больше решений20960899?

Вероятно, они используют алгоритм, не требующий брутфорсного перебора

А если и здесь будет алгоритм, а не прочий перебор?
29 мар 18, 12:07    [21295670]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
MBo
Member

Откуда:
Сообщений: 68
Gennadiy Usov,

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


Ну так его, видимо, и нужно придумать? Хорошая идея алгоритма может позволить если и не уйти
от экспоненциального роста сложности, то хотя бы понизить его показатель
29 мар 18, 12:15    [21295694]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1589
MBo
Gennadiy Usov,

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


Ну так его, видимо, и нужно придумать? Хорошая идея алгоритма может позволить если и не уйти
от экспоненциального роста сложности, то хотя бы понизить его показатель

Согласен.
Пока вижу одну трудность в алгоритме21283691, которая заключается в следующем:
чтобы выйти с алгоритмом, который находит большое множество решений, на доску 1001х1001 (или близкую к ней) 21035592, нужно найти возможность определения различных сочетаний для 250 чисел (количество независимых "четверок" ферзей на данной доске). А это где-то 9,04626E+74.
Такое число для выше указанного метода вряд ли подойдет: не влезет в ячейку. А если влезет, то пропадут всякие о-малые.
Поэтому необходимо несколько видоизменить алгоритм.
29 мар 18, 13:00    [21295868]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5 6 7 8 9   вперед  Ctrl      все
Все форумы / Программирование Ответить