ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск любых сочетаний из К чисел
25 сообщений из 206, страница 3 из 9
  3  все
Поиск любых сочетаний из К чисел
    #39622646
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Gennadiy Usov сочетания с 8 по 15 повторяют сочетания с 1 по 7 (с добавлением сочетания 0000) при добавлении сочетания 1, но уже со сдвигом по колонкам на 3 колонки.
То есть, мы имеем восьмеричную систему счисления. И имея в памяти только 8 сочетаний (с 1 по 7 плюс 0000), мы можем описать все сочетания в количестве 7,3787E+19.

Мы можем для удобства выстроить любую систему счисления, в зависимости от удобства, кратную 2.
Попробуем взглянуть на проблему по другому.
Имеем число А = 2 в степени 250.
Данное число можно представить как А = В в степени 10, где В = 2 в степени 25.
Количество сочетаний для 25 чисел равно 16777216. Данное число будет «считабельно». И все сочетания для 25 чисел поместим в массив С (25, 16777216), естественно, вместе с 00000….00000.
Осталось придумать алгоритм собирания 10 сочетаний по 25 из массива С в одно сочетание по 250.
...
Рейтинг: 0 / 0
29.03.2018, 13:25
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39623208
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Gennadiy UsovИмеем число А = 2 в степени 250.
Данное число можно представить как А = В в степени 10, где В = 2 в степени 25.
Количество сочетаний для 25 чисел равно 16777216. Данное число будет «считабельно». И все сочетания для 25 чисел поместим в массив С (25, 16777216), естественно, вместе с 00000….00000.
Осталось придумать алгоритм собирания 10 сочетаний по 25 из массива С в одно сочетание по 250.
Рассмотрим один из возможных алгоритмов, позволяющих решить данную задачу.
Допустим имеется массив сочетаний С(25, 16777216), массив сочетания С1 (250), массив счетчиков Р(10) и общий счетчик Р1.
Присвоим всем значениям счетчика значение 1:
Р( i ) = 1, 1 <= i <= 10, Р1 =1, Р2 = 16777216, где Р1 – счетчик сочетаний по 250.
Метка 1:
Далее основное присвоение:
цикл С1( j + 25 * (i – 1)) = С( j, Р( i ) ), 1 <= i <= 10, 1 <= j <= 25.
Р( 1 ) = Р( 1 ) + 1, Р1 = Р1 +1,
если Р( 1 ) > Р2 то
(Р( 1 ) = 1,
Р( i ) = Р( i ) +1, 2 <= i <= 10,
если Р( i ) <= Р2 то (переход к метке 1) иначе Р( i ) = 1).
Здесь массив С1 (250) - одномерный. Но можно его сделать двумерным с помощью счетчика Р1.
Можно рассмотреть другие варианты соотношений длины малых массивов и их количества : 10 и 25, 50 и 5, 5 и 50.
...
Рейтинг: 0 / 0
30.03.2018, 12:36
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39623266
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Gennadiy UsovТеперь появилась новая задачка:
Имеется несколько последовательностей чисел: 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 х К.
Перед тем как считать все сочетания в лоб, попробуем оценить количество сочетаний.
Разделим массив 1 + Кх2 на части:
в первую группу возьмем первые числа от 1 до К +1,
во вторую группу возьмем остальные К чисел.
Тогда в первой группе получается Р1 = (2 в степени (К + 1)) сочетаний чисел, а во второй группе получается Р2 = (2 в степени К ) сочетаний чисел.
Попробуем складывать сочетания из первой и второй группы.
В силу условий несовместимости отдельных чисел получается следующая зависимость:
при выборке по 1 числу из второй группы первая группа уменьшается в два раза,
при выборке по 2 числа из второй группы первая группа уменьшается в четыре раза,
при выборке по 3 числа из второй группы первая группа уменьшается в восемь раз,
…
При выборке всех чисел из второй группы имеем только 2 сочетаний из первой группы.
Осталось только сложить между собой произведения сочетаний (к по n ) на число (2 в степени (К + 1- к)).
Наверное, есть формула по определению таких сумм.
Может быть кто-то встречал такую формулу?
...
Рейтинг: 0 / 0
30.03.2018, 13:43
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39623277
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Gennadiy Usov,
формула по определению таких сумм безусловно есть, только знают её не только лишь все, мало кто вообще её знает.

А если б/сарказма, то можно попробовать метод производящих функций. Как раз есть возможность представить в рекуррентном виде.
...
Рейтинг: 0 / 0
30.03.2018, 14:04
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39623568
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
exp98Gennadiy Usov,
формула по определению таких сумм безусловно есть, только знают её не только лишь все, мало кто вообще её знает.

А если б/сарказма, то можно попробовать метод производящих функций. Как раз есть возможность представить в рекуррентном виде.
Спасибо!
Посмотрел производящие функции.
https://ru.wikipedia.org/wiki/Сочетание
Сумма сочетаний умноженных на х в степени к.
У нас х = 2. Только умножение идет на 2 в степени (К + 1- к).
С другой стороны, сочетание (к по n) равно сочетанию ( (n- к) по n). То есть, сумму произведений сочетаний на степень можно развернуть в другую сторону. И получается нормальная производящая функция, только значения каждой степени умноженное еще на 2. Следовательно, значение производящая функция равно:
2 х ( 1 + 2 ) (в степени n).
Кажется так.
Проверки на массивах вручную показали:
массив 3 – 6 сочетаний, массив 5 – 18 сочетаний, массив 7 – 54 сочетаний.
Следовательно, можно говорить, что для массива из 83 чисел имеем 2,66056E+39 сочетаний.
...
Рейтинг: 0 / 0
30.03.2018, 20:02
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39623676
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Замечен интересный момент периодичности или цикличности расположения сочетаний в массиве сочетаний из n цифр.
Для первой колонке справо имеем сначала 0, потом 1, затем 0 и опять 1, то есть 1 на 1.
Для второй колонки будет 2 на 2.
Для третьей колнки будет 4 на 4.
Для четвертой колонки будет 8 на 8.
и т. д.
Для колонки n будет Р на Р, где Р = 2 в степени n.
...
Рейтинг: 0 / 0
31.03.2018, 11:32
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39623760
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Gennadiy UsovАлгоритм 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
Теперь добавляем средние А чисел.
И смотрим, сколько теперь получается сочетаний.
В ручном режиме получилось следующее:
для трех цифр получается 5 сочетаний,
для шести цифр получается 25 сочетаний,
для девяти цифр получается 125 сочетаний.
Если рассмотреть все сочетания, то оказывается, что получается сумма произведений сочетаний (к по n) на число 4 в степени к. То есть, это производящие функции. И сумма этих произведений будет
(1 + 4 ) в степени n.
...
Рейтинг: 0 / 0
31.03.2018, 19:27
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39658892
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Сообщение. Алгоритм определения сочетаний чисел, часть из которых несовместима с другими числами.
Ранее в сообщениях 21302076 21300743 говорилось о сочетаниях таких чисел. Приводятся описание алгоритмов определения сочетаний.
...
Рейтинг: 0 / 0
09.06.2018, 14:19
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709272
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Как известно, количество сочетаний из К чисел равно 2^К.

Все эти сочетания можно разбить на пары, которые в «сумме» дадут сочетание 111111…1111. Если требуется оставить из этих пар только одно сочетание, а также убрать сочетания 00000....000 и 1111…111, то останутся 2^(К-1)-1 сочетаний.

Попробую написать программу для поиска таких сочетаний.
...
Рейтинг: 0 / 0
27.09.2018, 13:46
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709512
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
Gennadiy Usov,
чего там искать: 00001....01111
...
Рейтинг: 0 / 0
27.09.2018, 20:03
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709515
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Gennadiy UsovКак известно, количество сочетаний из К чисел равно 2^К.

то о чем вы пишите есть количество подмножеств множества из k элементов,
...
Рейтинг: 0 / 0
27.09.2018, 20:06
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709520
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovКак известно, количество сочетаний из К чисел равно 2^К.

Все эти сочетания можно разбить на пары, которые в «сумме» дадут сочетание 111111…1111. Если требуется оставить из этих пар только одно сочетание, а также убрать сочетания 00000....000 и 1111…111, то останутся 2^(К-1)-1 сочетаний.

Попробую написать программу для поиска таких сочетаний.
У вас - пробелы в дискретной математике.

Почитайте здесь http://vyshka.math.ru/pspdf/s09/discrete/DiscrMath09Chap1.pdf

Перестановки, сочетания, размещения . Это разные понятия.

В ферзевой задаче я использовал перестановки ладей.
...
Рейтинг: 0 / 0
27.09.2018, 20:26
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709521
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
MBoGennadiy Usov,
чего там искать: 00001....01111То, что точки в двух сочетаниях 00000....000 и 1111…111, это в левом 0, в правом 1, просто 0 или 1 очень много в каждом сочетании.

Идея в чем: есть сочетания 00010011 и 11101100. Мне нужно одно из этих сочетаний исключить (не рассматривать).
И так для всех сочетаний (пар сочетаний).
...
Рейтинг: 0 / 0
27.09.2018, 20:29
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709522
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovИдея в чем: есть сочетания 00010011 и 11101100. Мне нужно одно из этих сочетаний исключить (не рассматривать).
И так для всех сочетаний (пар сочетаний).
Если не ошибаюсь то достаточно перебрать все сочетания до 01111111, т.е. до 2^(К-1)
...
Рейтинг: 0 / 0
27.09.2018, 20:33
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709523
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonУ вас - пробелы в дискретной математике.
Почитайте здесь http://vyshka.math.ru/pspdf/s09/discrete/DiscrMath09Chap1.pdf
Перестановки, сочетания, размещения . Это разные понятия.
В ферзевой задаче я использовал перестановки ладей.Я применил статью
https://ru.wikipedia.org/wiki/Сочетание

Мы с Вами говорим о разных задачах:
- Вы говорите о перестановке ладей (ферзей);
- я говорю о сочетаниях по работе с разными элементами задачи(с какими элементами должны работать в настоящий момент). Это не обязательно ферзи. Это могут быть двойки, тройки, четверки, пятерки и т.д. ферзей.

Поэтому я применяю термин сочетания.
...
Рейтинг: 0 / 0
27.09.2018, 20:39
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709526
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TGennadiy UsovИдея в чем: есть сочетания 00010011 и 11101100. Мне нужно одно из этих сочетаний исключить (не рассматривать).
И так для всех сочетаний (пар сочетаний).Если не ошибаюсь то достаточно перебрать все сочетания до 01111111, т.е. до 2^(К-1)С точки зрения количества - верно. А вот подряд перебирать сочетания не получится.

Самый лучший способ проверить - это сделать все сочетания для 3-х (001, 010, 100), 4-х и 5-ти чисел (объектов).
...
Рейтинг: 0 / 0
27.09.2018, 20:44
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709527
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovmaytonУ вас - пробелы в дискретной математике.
Почитайте здесь http://vyshka.math.ru/pspdf/s09/discrete/DiscrMath09Chap1.pdf
Перестановки, сочетания, размещения . Это разные понятия.
В ферзевой задаче я использовал перестановки ладей.Я применил статью
https://ru.wikipedia.org/wiki/Сочетание

Мы с Вами говорим о разных задачах:
- Вы говорите о перестановке ладей (ферзей);
- я говорю о сочетаниях по работе с разными элементами задачи(с какими элементами должны работать в настоящий момент). Это не обязательно ферзи. Это могут быть двойки, тройки, четверки, пятерки и т.д. ферзей.

Поэтому я применяю термин сочетания.
Вы написали.
Gennadiy UsovКак известно, количество сочетаний из К чисел равно 2^К.
Это - некорректно. 2^K - не имеет никакого отношения к термину сочетания .

Я вас поправил.
...
Рейтинг: 0 / 0
27.09.2018, 20:44
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709619
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Используя опыт построения сочетаний для 2, 3, 4, 5 объектов в количестве одного из пары,
можно сделать следующую программу:
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
// K – количество чисел (объектов).
var P = new Array(K+1);
var i1;  

for(var i = 1; i <= K; i++) P[i]=0;

var K1 = K-3;
for(var p1 = 0; p1<= K1; i++) {
               If (p1 > 0) {
                           I1=1;
                      D:
                           P[i1]=P[i1]+1;
                           If (P[i1] == 2) {
                                              P[i1] = 0;
                                              i1=i1+1;
                                              go to D;
                           }
              }

              for(var i2 = (i1+1); i2<= K; i++) {
                           P[i2]=1:

                         // получаем сочетание P[K] (либо 0, либо 1)

                           P[i2] = 0;
              }
}

В данном виде программа позволяет получить массив сочетаний, так как все сочетаний формируются в цикле (и не в одном).
Поскольку сочетаний может быть очень много, то целесообразно сделать эту программу в виде процедуры, чтобы «вытаскивать» только одно очередное сочетание, по порядку.
...
Рейтинг: 0 / 0
28.09.2018, 07:31
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709804
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
В предыдущем сообщении 21688676 операторы:
Код: javascript
1.
2.
var K1 = K-3;
for(var p1 = 0; p1<= K1; i++) {

нужно заменить на операторы:
Код: javascript
1.
2.
var K1 = 2^(K-3)-1;
for(var p1 = 0; p1<= K1; i++) {
...
Рейтинг: 0 / 0
28.09.2018, 13:04
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709810
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
И ещё заменить операторы
Код: javascript
1.
2.
3.
for(var p1 = 0; p1<= K1; i++) {
            .....
              for(var i2 = (i1+1); i2<= K; i++) {

на операторы
Код: javascript
1.
2.
3.
for(var p1 = 0; p1<= K1; р1++) {
            .....
              for(var i2 = (i1+1); i2<= K; i2++) {
...
Рейтинг: 0 / 0
28.09.2018, 13:10
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709813
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Кстати, можно немного упростить программу 21688676 с учетом последующих изменений с целью определения всех сочетаний:

Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
// K – количество чисел (объектов).
var P = new Array(K+1);
var i1;  

for(var i = 1; i <= K; i++) P[i]=0;

var K1 = 2^K-1;
for(var p1 = 1; p1<= K1; p1++) {
                           i1=1;
                      D:
                           P[i1]=P[i1]+1;
                           if (P[i1] == 2) {
                                              P[i1] = 0;
                                              i1=i1+1;
                                              go to D;
                           }

                         // получаем сочетание P[K] (либо 0, либо 1)
}
...
Рейтинг: 0 / 0
28.09.2018, 13:18
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709829
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy Usov, не совсем понимаю что должно получиться. Можно пример для K = 3 ?
...
Рейтинг: 0 / 0
28.09.2018, 13:40
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709839
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy Usov,

JavaScript не умеет возводить в степень так как вы описали.

С одной стороны похвально что вы пытаетесь помочь. С другой стороны это выглядит как медвежья услуга.

И помогли и запутали.
...
Рейтинг: 0 / 0
28.09.2018, 13:55
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709886
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TGennadiy Usov, не совсем понимаю что должно получиться. Можно пример для K = 3 ?Вы задали вопрос, а я нашел ошибку: при р1=0 не определен i1. Поэтому вместо:
Код: javascript
1.
2.
for(var p1 = 0; p1<= K1; p1++) {
               if (p1 > 0) {

будут операторы:
Код: javascript
1.
2.
3.
for(var p1 = 0; p1<= K1; p1++) {
               i1=0;
               if (p1 > 0) {

При К = 3 должно получиться 100, 010, 001.
...
Рейтинг: 0 / 0
28.09.2018, 15:00
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39709899
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovПри К = 3 должно получиться 100, 010, 001.
А при К = 4 добавится 1000, 0100, 0010, 0001. Так ?

Если так то это К вариантов, а не 2^(K-1)

И показанное это степени двойки, если рассматривать эти числа как двоичные, т.е.
Код: sql
1.
2.
3.
4.
2^0 = 0b0001 = 1
2^1 = 0b0010 = 2
2^2 = 0b0100 = 4
2^3 = 0b1000 = 8
...
Рейтинг: 0 / 0
28.09.2018, 15:13
| Ответить | Цитировать | Написать  
25 сообщений из 206, страница 3 из 9
  3  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск любых сочетаний из К чисел
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]