ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Генерация сочетаний из N по K
25 сообщений из 174, страница 4 из 7
  4  все
Генерация сочетаний из N по K
    #40039062
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

на практике наиболее удобным вариантом оказывается использование исходников,
в которых предусмотрены обратные вызовы функций обработки.
...
Рейтинг: 0 / 0
26.01.2021, 16:59
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039068
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
На сях с бустом есть такое https://www.boost.org/doc/libs/1_70_0/libs/coroutine/doc/html/coroutine/intro.html

А есть в Delphi?
...
Рейтинг: 0 / 0
26.01.2021, 17:15
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039072
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

с бустом ))
...
Рейтинг: 0 / 0
26.01.2021, 17:27
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039077
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Интересно, что если генерировать сочетания в нисходящем порядке,
то минимальное значение элемента в каждой позиции совпадет с номером позиции.
По идее, это упрощает алгоритм и позволяет обойтись минимумом вычислений.

Например, сочетания по 4 из 6 для множества {0,1,2,3,4,5} выводятся в таком порядке:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
2345
1345
0345
1245
0245
0145
1235
0235
0135
0125
1234
0234
0134
0124
0123



Алгоритм получился довольно быстрым
Код: pascal
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.
procedure GenerateCombinationDesc(p: pIntegerArray; n, k: integer);
var
  len: integer;
begin;
  len:=k;
  dec(k);
  while true do begin;
    dec(n);
    while k>0 do begin;
      p[k]:=n;
      dec(k);
      dec(n);
      end;
    repeat;
      p[0]:=n;
      dec(n);
      //inc(cnt);
      //ShowCombinationDesc(p, len); //обработка сочетания p[0..k-1]
      until n<0;
    repeat;
      inc(k); if k>=len then exit;
      n:=p[k];
      until k<n;
    end;
  end;
...
Рейтинг: 0 / 0
26.01.2021, 17:42
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039087
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, так а в исходном варианте разве не тоже самое?


Код: sql
1.
2.
3.
4.
5.
6.
1 2 3
1 2 4
1 3 4
2 3 4
------
1 2 3 (min)
...
Рейтинг: 0 / 0
26.01.2021, 18:16
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039088
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov
mayton,

с бустом ))

Ну я не против. Есть ли в Делфях свой буст?
...
Рейтинг: 0 / 0
26.01.2021, 18:17
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039090
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
Aleksandr Sharahov, так а в исходном варианте разве не тоже самое?


Код: sql
1.
2.
3.
4.
5.
6.
1 2 3
1 2 4
1 3 4
2 3 4
------
1 2 3 (min)



Не совсем то же самое.
Когда мы наращиваем значения элементов,
то закончим при достижении значения,
которое отличается на дельту (n-k) от индекса элемента.

т е минимальное не является финальным
...
Рейтинг: 0 / 0
26.01.2021, 18:26
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039092
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
Aleksandr Sharahov
mayton,

с бустом ))

Ну я не против. Есть ли в Делфях свой буст?


Есть несколько библиотек для параллельной работы,
я не знаю, насколько они сопоставимы с бустом.
...
Рейтинг: 0 / 0
26.01.2021, 18:28
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039093
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov
mayton
пропущено...

Ну я не против. Есть ли в Делфях свой буст?


Есть несколько библиотек для параллельной работы,
я не знаю, насколько они сопоставимы с бустом.

Чорт с ним. Корутитны? Континуэйшены есть?
...
Рейтинг: 0 / 0
26.01.2021, 18:29
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039097
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
Aleksandr Sharahov
пропущено...


Есть несколько библиотек для параллельной работы,
я не знаю, насколько они сопоставимы с бустом.

Чорт с ним. Корутитны? Континуэйшены есть?


1. Если потребуется, всегда можно эмулировать.
2. Но если кто-то скажет, что у него интерфейс заточен таким образом,
то нафига оно надо, если можно без него.
...
Рейтинг: 0 / 0
26.01.2021, 18:46
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039100
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov
mayton
пропущено...

Чорт с ним. Корутитны? Континуэйшены есть?


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

Твоя реализация - в конечном варианте не-рекурсивная. Поэтому тебе это не надо.
Можно сказать что ты избежал этой участи

Но в топике я также поставил сверх-задачу - обобщить подходы к рекурренным алгоритмам. В частности
к итераторам. Я не буду настаивать. Ведь рекурсия - это сугубо мой интерес. В частности технологические
штуки такие как
  • boost/coroutine (boost)
  • channels (GoLang)
  • delayed lists, streans (MIT-Scheme)
раз я достану из кармана алгоримы на графах и там такой трюк может не проскочить. И размотка
рекурсии в дек или в очередь может быть нетривиальной задачей или просто очень хлопотной
в количестве кода.

Поэтому я хочу оставить рекурсивное решение Анатолия. Оно мне нравится. Но сделать его
более технологичным. Тоесть пригодным к интеграции и использованию извне.
...
Рейтинг: 0 / 0
26.01.2021, 19:01
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039104
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton

Твоя реализация - в конечном варианте не-рекурсивная. Поэтому тебе это не надо.
Можно сказать что ты избежал этой участи


Их есть у меня )
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
procedure RecursiveCombination(p: pIntegerArray; n, k: integer);
var
  i: integer;
begin;
  if k<0 then inc(cnt)
  else for i:=k to n do begin;
    p[k]:=i;
    RecursiveCombination(p, i-1, k-1)
    end;
  end;

var
  c: TCombination;
begin;
  cnt:=0;
  SetLength(c, 6);
  RecursiveCombination(@c[0], 100-1, 6-1);
end.
...
Рейтинг: 0 / 0
26.01.2021, 19:10
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039113
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T

Еле нагуглил как привести reverse_iterator к iterator
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
bool next_combinations(std::vector<int>& a, int max) noexcept {
	for (auto rit = a.rbegin(); rit != a.rend(); rit++, max--) {
		assert(*rit >= 1 && *rit <= max);
		if (*rit < max) {
			(*rit)++;
			for (std::vector<int>::iterator it(rit.base()); it != a.end(); it++) *it = *(it - 1) + 1;
			return true;
		}
	}
	return false;
}


ОК. Ну я скоро запутаюсь в исходниках. Ты еще не создавал репку? У каждого автора уже более чем 1 вариант кода.
...
Рейтинг: 0 / 0
26.01.2021, 20:09
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039116
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Давайте уже подумаем над API использования этого софта.

Как по мне - процесс consumer не сможет заглотить ни STDOT ни vector<vector<int>>. Неудобно это в одном случае.
И не хватит памяти в другом.

Надо думать над умной коммуникацией. Подумайте вот если-бы вы использовали бинарник этого генератора
то каким образом-бы вы забирали результаты этой генерации.

ИМХО Правильнее получать следующее значение, т.е. есть массив с текущим значением, вызываешь функцию, она внутри превращает массив в следующее, обрабатываешь, получаешь следующее и т.д.
Реализации когда генератор внутри себя выдает значения куда-то там - нечитабельны, т.к. код получается корявый.
...
Рейтинг: 0 / 0
26.01.2021, 20:18
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039117
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
ОК. Ну я скоро запутаюсь в исходниках. Ты еще не создавал репку? У каждого автора уже более чем 1 вариант кода.

Нормальный этот 22268624 остальные можешь не смотреть.
...
Рейтинг: 0 / 0
26.01.2021, 20:20
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039126
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давайте зайдем в "области тьмы". В временую сложность.

Что такое сочетания из 2 по 10 тыщ? Фигня. Щас дам калькулятор.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
scala> def fact(x: BigInt): BigInt = (BigInt(1) to x).foldLeft(BigInt(1))(_ * _)
fact: (x: BigInt)BigInt

scala> def combinations(k: Long, n: Long): BigInt = ( fact(BigInt(n)) / (fact(BigInt(k)) * fact(BigInt(n - k)) ) )
combinations: (k: Long, n: Long)BigInt

scala> combinations(2,10000)
res2: BigInt = 49995000



Это 49 миллионов унылых пар чисел наподобие

Код: sql
1.
2.
3.
4.
1,2
1,3
1,4
9999,10000



и так далее. Как в морском бое. Когда мы заполняем пол-поля треугольником по диагонали.

В топиках простых чисел мы и поболее считывали.

Вот мой concern в чем заключается. Внешний вид алгоритма имеющего квадратичные накладные расходы.

Код: sql
1.
2.
3.
4.
5.
6.
	for (int i = k - 1, max = n; i >= 0; i--, max--) {
		assert(a[i] >= 1 && a[i] <= max);
		if (a[i] < max) {
			a[i]++;
			i++;
			for (; i < k; i++) a[i] = a[i-1] + 1;


Надо поисследовать как ведет себя итеративный алгоритм на малых значениях k при очень больших значениях n.
...
Рейтинг: 0 / 0
26.01.2021, 21:11
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039127
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Давайте зайдем в "области тьмы". В временую сложность.

Что такое сочетания из 2 по 10 тыщ? Фигня. Щас дам калькулятор.

Это в уме считается, без калькулятора:
Код: plaintext
10000! / (9998! * 2!) = 10000 * 9999 / 2 = 5000 * 9999 = чуть меньше 50 млн.
...
Рейтинг: 0 / 0
26.01.2021, 21:27
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039128
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да. Этот калькулятор - уродский. Я писал его на коленке.

Код: sql
1.
( fact(BigInt(n)) / (fact(BigInt(k)) * fact(BigInt(n - k)) ) )


Слишком большой числитель и знаменатель при мизерном частном. Соотв надо сократить еще до вычислений факториалы.
...
Рейтинг: 0 / 0
26.01.2021, 21:30
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039129
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
 
А лямбда похожа на ж0пу

Код: sql
1.
(_ * _)

...
Рейтинг: 0 / 0
26.01.2021, 21:33
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039132
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Правильнее этот 22268468 , он быстр и уродлив одновременно, он быстрее, но непонятней. Запихать его в либу можно, попытаться объяснить кому-то как он работает - сложно.
...
Рейтинг: 0 / 0
26.01.2021, 21:42
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039134
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T
Правильнее этот 22268468 , он быстр и уродлив одновременно, он быстрее, но непонятней. Запихать его в либу можно, попытаться объяснить кому-то как он работает - сложно.

Это-же и есть самый важный скилл. Объяснить ребёнку как оно работает

Пускай внутри коробочки будет Ад и Израиль. А снаружи - розовые единороги.
...
Рейтинг: 0 / 0
26.01.2021, 21:46
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039145
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Это-же и есть самый важный скилл. Объяснить ребёнку как оно работает

ага, поэтому сначала я родил первый вариант думая от лица процессора, потом переделал в пользу читаемости, потом понял почему второй вариант тормознее, там лишних действий больше, но все-равно я за него.
...
Рейтинг: 0 / 0
26.01.2021, 22:03
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039165
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dima T

Запусти мой all_combinations_6(100)
Код тут 22268813
Интересно сколько времени он у тебя считается.

0.6c
...
Рейтинг: 0 / 0
27.01.2021, 00:13
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039175
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
думаю, аналог 22269637 на c не сильно отстанет
...
Рейтинг: 0 / 0
27.01.2021, 01:11
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039188
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T

добавь ключи -O3 -DNDEBUG

Вот среди ночи я добрался до своего десктопа. Щас посмотрим.
...
Рейтинг: 0 / 0
27.01.2021, 01:57
| Ответить | Цитировать | Написать  
25 сообщений из 174, страница 4 из 7
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Генерация сочетаний из N по K
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=40039117&tid=1339689]:
 0ms
get settings:
 10ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 55ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 78ms
get tp. blocked users:
 2ms
others: 251ms
total:  433ms
созд. / загр.: 433ms
x
x
Закрыть


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