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

C(k,n) = n! / (n - k)! * k!

Я не считал. Тут надо просто факториал заменять на гладкую функцию
но субъективно... если смотреть на треугольник Паскаля - то мемоизировать
нужно самый центр и низ треугольника где значения большие.

А на краях они достаточно малы и там нечего считать.

 
...
Рейтинг: 0 / 0
25.01.2021, 15:04
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038709
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T

Взять ту же задачу милторга, я так понимаю у него вектора были фиксированного размера, т.е. известного на момент компиляции.

Я думаю что нам не стоит завязываться на те задачи. Там - фигня на постном масле а у нас обобщенный подход.
...
Рейтинг: 0 / 0
25.01.2021, 15:25
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038721
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Dima T, по этой формуле

C(k,n) = n! / (n - k)! * k!

Я не считал. Тут надо просто факториал заменять на гладкую функцию
но субъективно... если смотреть на треугольник Паскаля - то мемоизировать
нужно самый центр и низ треугольника где значения большие.

А на краях они достаточно малы и там нечего считать.

(n - k)! * k! убывает по мере увеличения k, т.е. максимальное количество сочетаний будет в середине при k = n/2
...
Рейтинг: 0 / 0
25.01.2021, 15:43
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038752
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это верно отчасти. Если зафиксировать N.

Но у нас функция двух аргументов и для нее максимум и экстремумы зависят от n,k в совокупности.
...
Рейтинг: 0 / 0
25.01.2021, 17:15
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038757
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я вот что подумал: если мою функцию с фиксированным k чуть переделать чтобы она охватывала диапазон не 1...n, а m...n, то она вполне себе применима для генерации всех вариантов последних k разрядов.

Т.е. первые разряды меняем универсальным способом, а для последних k вызываем функцию и внутри нее снимаем результаты.
...
Рейтинг: 0 / 0
25.01.2021, 17:41
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038758
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Можешь на примере сочетаний показать? Непонятно....
...
Рейтинг: 0 / 0
25.01.2021, 17:47
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038760
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Например С(4,6)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 4 5
1 3 4 6
1 3 5 6
1 4 5 6
2 3 4 5
2 3 4 6
2 3 5 6
2 4 5 6
3 4 5 6

Допустим есть функция с3(m,n), которая выдает все сочетания по 3 в диапазоне m...n, далее первый разряд перебираем снаружи и вызываем c3() для генерации последних 3х разрядов
Код: plaintext
1.
2.
1 c3(2,6)
2 c3(3,6)
3 c3(4,6)
...
Рейтинг: 0 / 0
25.01.2021, 18:00
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038765
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ты хочешь мемоизировать последние 4 разряда? Ну ОК. Попробуй. Главное чтоб результат совпал с полным вариантом.
...
Рейтинг: 0 / 0
25.01.2021, 18:08
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038778
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,

сорри что встреваю, но тебе может оказаться интересным:

В Oracle, начиная с 10й версии есть готовая sql-функция под это - POWERMULTISET_BY_CARDINALITY:

Код: plsql
1.
2.
select rownum as rn, cast(column_value as sys.ku$_ObjNumSet) as a_set
from table(POWERMULTISET_BY_CARDINALITY(sys.ku$_ObjNumSet(1,2,3,4,5,6),4)) t



 

упс... что-то поломалось, но на любом sqlfiddle это можно проверить...


что касается разбивки на диапазоны, то весь процесс можно представить как манипуляцию k-м разрядом + сдвиг.
т.е. - если к-1 разряд фиксирован, то для к-го - n-k+1 вариант заполнения.
затем "затираем" значение к-1 разряда (сдвигаем набор на единицу вправо), получаем еще n-k комбинаций.
...
сдвигая последовательно лесенкой разряды от к до n-k-1 получим все комбинации, но в другом порядке выдачи.
Это как идея без кода, мимоходом...
т.е. идея состоит в построении соответствия номера комбинации подходящему "сдвигу" и "номеру операции внутри него".
Тогда, может быть, все разбивается на набор независимых циклов в пределах "сдвигов"
...
Рейтинг: 0 / 0
25.01.2021, 18:58
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038780
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
booby, OK посмотрю. У меня растет объем технического долга по топику. Я еще Сашин исходник не смотрел
и не скомпилировал целиком.
...
Рейтинг: 0 / 0
25.01.2021, 19:00
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038799
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Ты хочешь мемоизировать последние 4 разряда? Ну ОК. Попробуй. Главное чтоб результат совпал с полным вариантом.

"мемоизировать" тут не в тему, т.к. надо разные наборы, они не повторяются.
...
Рейтинг: 0 / 0
25.01.2021, 20:27
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038819
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Оптимизировал немного рекурсивный и нерекурсивный алгоритмы.
Для 6 из 100, рекурсивный теперь дает 1с, нерекурсивный 1.2с

Исходники (цветом выделил изменения)
 
Рекурсивный
Код: plaintext
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.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
#include <iostream>
#include <vector>

#define LIKELY(x)       __builtin_expect(!!(x), 1)
#define UNLIKELY(x)     __builtin_expect(!!(x), 0)

class RecursiveCombinator
{
public:
    RecursiveCombinator(size_t k, std::vector<int> items, bool print)
        : k(k)
        , n(items.size())
        , items(std::move(items))
        , print(print)
    {
        curr.resize(k);
    }

    void generate() noexcept
    {
        std::cout << "k=" << k << ", n=" << n << ", print=" << print << "\n";
        size_t count = generate(0, 0, 0);
        std::cout << "total: " << count << "\n";
    }

private:
    // алгоритм
    size_t generate(size_t pos, size_t val, size_t count) noexcept
    {
        const size_t limit = n - k  + pos + 1;
        for (; val < limit; val++) {
            curr[pos] = val;
            if (pos == last_pos) {
                count++;
                print_current();    
            }
            else {
                count = generate(pos + 1, val + 1, count);
            }
        }
        return count;
    }

    void print_current() noexcept
    {
        if (UNLIKELY(print)) {
            for (size_t i = 0; i < k; i++) {
                std::cout << items[curr[i]] << " ";
            }
            std::cout << "\n";
        }
    }

private:
    const size_t k;
    const size_t n;
    const size_t last_pos = k - 1;
    const std::vector<int> items;
    const bool print;
    std::vector<size_t> curr;
};


std::vector<int> iota(size_t n)
{
    std::vector<int> rv(n);
    for (size_t i = 0; i < n; i++) {
        rv[i] = i + 1;
    }
    return rv;
}

int main(int argc, char* argv[])
{
    std::cout.sync_with_stdio(false);
    size_t k = 3;
    int n = 4;
    bool print = true;
    if (argc > 2) {
        k = atol(argv[1]);
        n = atol(argv[2]);
    }
    if (argc > 3) {
        print = argv[3][0] == 'p';
    }
    RecursiveCombinator comb{k, iota(n), print};
    comb.generate();
    return 0;
}





 
Нерекурсивный
Код: plaintext
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.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
#include <iostream>
#include <vector>

#define LIKELY(x)       __builtin_expect(!!(x), 1)
#define UNLIKELY(x)     __builtin_expect(!!(x), 0)


class NonRecursiveCombinator
{
public:
    NonRecursiveCombinator(size_t k, std::vector<int> items, bool print)
        : k(k)
        , n(items.size())
        , items(std::move(items))
        , print(print)
    {
        curr.resize(k);
    }

    void generate() noexcept
    {
        std::cout << "k=" << k << ", n=" << n << ", print=" << print << "\n";
        size_t count = generate_impl();
        std::cout << "total: " << count << "\n";
    }

private:
    // алгоритм
    size_t generate_impl() noexcept __attribute((noinline))
    {
        size_t pos = 0;
        size_t limit = n - k + pos + 1;
        const size_t last_pos = k - 1;
        size_t val = 0;
        size_t count = 0;
        while (true) {
            for (; val < limit; val++) {
                curr[pos] = val;
                if (pos == last_pos) {
                    count++; 
                    print_current();
                }
                else {
                    pos++;
                    limit++;
                }
            }
            if (pos == 0)
                break;
            pos--;
            limit--;
            val = curr[pos] + 1;
        }
        return count;
    }

    void print_current() noexcept 
    {
        if (UNLIKELY(print)) {
            for (size_t i = 0; i < k; i++) {
                std::cout << items[curr[i]] << " ";
            }
            std::cout << "\n";
        }
    }

private:
    const size_t k;
    const size_t n;
    const std::vector<int> items;
    const bool print;
    std::vector<size_t> curr;
    size_t count = 0;
};


std::vector<int> iota(size_t n)
{
    std::vector<int> rv(n);
    for (size_t i = 0; i < n; i++) {
        rv[i] = i + 1;
    }
    return rv;
}

int main(int argc, char* argv[])
{
    std::cout.sync_with_stdio(false);
    size_t k = 3;
    int n = 4;
    bool print = true;
    if (argc > 2) {
        k = atol(argv[1]);
        n = atol(argv[2]);
    }
    if (argc > 3) {
        print = argv[3][0] == 'p';
    }
    NonRecursiveCombinator comb{k, iota(n), print};
    comb.generate();
    return 0;
}


...
Рейтинг: 0 / 0
25.01.2021, 23:02
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038831
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я обычно такой "for" разворачиваю в while.

Смысл в том что val++ теперь стоит ниже тела цикла и причинно-следственная связь логичнее смотрится.
Как в структурном программировании.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
        while (val < limit) {
            curr[pos] = val;
            if (pos == last_pos) {
                count++;
                print_current();    
            } else {
                count = generate(pos + 1, val + 1, count);
            }
            val++
        }
...
Рейтинг: 0 / 0
26.01.2021, 00:14
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038869
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Попробовал на вектор переделать и с итераторами переписать
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
bool next_combinations(std::vector<int>& a, int max) noexcept {
	for (auto it = a.end() - 1; it >= a.begin(); it--, max--) {
		assert(*it >= 1 && *it <= max);
		if (*it < max) {
			(*it)++;
			it++;
			for (; it != a.end(); it++) *it = *(it - 1) + 1;
			return true;
		}
	}
	return false;
}


Работает правильно, но вместо того чтобы выйти вылетаем с исключением Expression: can't decrement vector iterator before begin

Оно так и задумано что как только it ушел за начало, надо цикл завершать.

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

PS В релизе работает, там похоже нет этой проверки.
...
Рейтинг: 0 / 0
26.01.2021, 09:29
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038871
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Anatoly Moskovsky
Для 6 из 100, рекурсивный теперь дает 1с, нерекурсивный 1.2с

Запусти мой all_combinations_6(100)
Код тут 22268813
Интересно сколько времени он у тебя считается.
...
Рейтинг: 0 / 0
26.01.2021, 09:33
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038940
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
booby, OK посмотрю. У меня растет объем технического долга по топику. Я еще Сашин исходник не смотрел
и не скомпилировал целиком.


вот этот вариант побыстрее будет:
Код: 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.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
type
  TCombination = array of integer;

var
  cnt: integer;

//только для отладки
procedure ShowCombination(const c: TCombination);
var
  s: AnsiString;
  i: integer;
begin;
  for i:=0 to Length(c)-1 do s:=s+AnsiChar(Ord('A')+c[i]);
  //Form1.Memo1.Lines.Add(s);
  WriteLn(s);
  end;

procedure ProcessCombination(const c: TCombination);
begin;
  //ShowCombination(c); //отладка - закомментировать

  //тут делаем что-то с массивом
  inc(cnt);
  end;

//перебор сочетаний из n элементов [0..n-1] по k в алфавитном порядке
procedure GenerateCombinations(n, k: integer);
var
  c: TCombination;
  i, istart, v: integer;
begin;
  if (k<=0) or (k>n) then exit;

  SetLength(c, k);
  dec(n);
  dec(k);
  for i:=0 to k do c[i]:=i;
  ProcessCombination(c);

  //если существует более одного сочетания, то крутим цикл
  if k<n then begin;
    istart:=k;
    repeat;
      i:=istart;
      v:=c[istart];
      repeat;
        inc(v); c[i]:=v; inc(i);
        until i>k;
      ProcessCombination(c);
      if v<>n then begin;
        repeat;
          inc(v); c[k]:=v;
          ProcessCombination(c);
          until v=n;
        istart:=k;
        end;
      dec(istart);
      until istart<0;
    end;
  end;

cnt:=0;
GenerateCombinations(100, 6);
...
Рейтинг: 0 / 0
26.01.2021, 12:11
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038946
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, скользкий случай.

Я-бы по возможности по максимуму избегал в итераторах использовать арифметику и сравнение на больше либо равно.
Просто так. Личное предпочтение. Не всегда ведь он вектор. Может быть и список и дерево.

Вот тут описаны категории итераторов https://www.cplusplus.com/reference/iterator/
Может там - больше информации по debug. Возможно в отладке включены дополнительные
asserts которые и спасают код от всяких неосторожных действий в будущем.
...
Рейтинг: 0 / 0
26.01.2021, 12:22
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038970
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
mayton
Кодогенерация для С++ в рантайме? .... Хм... эту тему надо вообще толкнуть отдельным топиком.

Насколько я помню тут ключевой вопрос - безопасность. В рантайме ты должен сгенерить неподписанную
никем *.dll -ку и динамически вызвать ее из главной процедуры. Антивирус сойдет с ума.

Это то что легко делается в языках типа JScript/Python/Node/Lisp через eval и то что почти
неизведанно как Антарктида в С++.

Куча софта делает генерацию кода без проблем.
Везде где есть JIT трансляция.
Отдельная DLL нее нужна. Просто выделяешь память, копируешь туда код и помечаешь ее исполняемой.
...
Рейтинг: 0 / 0
26.01.2021, 13:11
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038972
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Нашел, есть reverse_iterator для перебора в обратном порядке http://www.cplusplus.com/reference/vector/vector/rbegin/

Еле нагуглил как привести 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;
}


Скорость такая же как с массивом 22268624
 
Исходник целиком, для компиляции
Код: plaintext
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.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <vector>

// Следующее сочетание k элементов диапазона 1...n в массив a[]
// Возвращает true если оно есть
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;
}

//**********************************************
int main(int argc, char**argv)
{
	int k, n;
	if (argc > 2) {
		k = atoi(argv[1]);
		n = atoi(argv[2]);
	} else {
		printf("Too few arguments\n");
		return 0;
	}

	printf("C(%d, %d)\n", k, n);
	std::vector<int> a;
	for (int i = 0; i < k; i++) a.push_back(i + 1);

	int cnt = 0;
	do {
		cnt++;
#ifdef _DEBUG
		for (int i = 0; i < k; i++) printf("%d ", a[i]);
		printf("\n");
#else
		if((cnt & 0x3FFFFFF) == 0) printf("Total: %d\r", cnt);
#endif
	} while (next_combinations(a, n));

	printf("Total: %d\n", cnt);
#if defined(_WIN32) || defined(_WIN64)
	printf("Time %d ms", clock());
#endif
	return 0;
}

...
Рейтинг: 0 / 0
26.01.2021, 13:12
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40038996
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Anatoly Moskovsky
mayton
Кодогенерация для С++ в рантайме? .... Хм... эту тему надо вообще толкнуть отдельным топиком.

Насколько я помню тут ключевой вопрос - безопасность. В рантайме ты должен сгенерить неподписанную
никем *.dll -ку и динамически вызвать ее из главной процедуры. Антивирус сойдет с ума.

Это то что легко делается в языках типа JScript/Python/Node/Lisp через eval и то что почти
неизведанно как Антарктида в С++.

Куча софта делает генерацию кода без проблем.
Везде где есть JIT трансляция.
Отдельная DLL нее нужна. Просто выделяешь память, копируешь туда код и помечаешь ее исполняемой.

Это офигенская тема. Вы пока тут - не развивайте. Я в пятницу подниму топик.
Но нас будет интересовать JIT для классических компилируемых языков (С++).
Платформеры и так этот жыд имеют.
...
Рейтинг: 0 / 0
26.01.2021, 14:08
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039008
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Anatoly Moskovsky
Оптимизировал немного рекурсивный и нерекурсивный алгоритмы.
Для 6 из 100, рекурсивный теперь дает 1с, нерекурсивный 1.2с

Хотел потестить, но не MSVC2019 не хочет компилировать рекурсивный

Код: plaintext
error C3861: '__builtin_expect': identifier not found
на строке
Код: plaintext
1.
if (UNLIKELY(print)) {



если тут написать
Код: plaintext
1.
if (print) {


то компилируется, но скорость работы чуть медленнее 1.7 сек.

Если закамментить все внутри print_current() то скорость 1.2 сек., против 1.6 сек прошлого варианта.

Но есть подозрение что полный каммент разрешает оптимизатору ломать этот цикл
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
   size_t generate(size_t pos, size_t val, size_t count) noexcept
    {
        const size_t limit = n - k + pos + 1;
        for (; val < limit; val++) {
            curr[pos] = val; // pos не меняется, при pos == last_pos можно за циклом curr[pos] = limit
            if (pos == last_pos) {
                count++; // Можно вынести за цикл как count += limit - val
                print_current();
            } else {
                count = generate(pos + 1, val + 1, count);
            }
        }
        return count;
    }
...
Рейтинг: 0 / 0
26.01.2021, 14:29
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039013
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИМХО в твоем случае, и в моем с фиксированным K 22268813 надо в параметрах передавать указатель на функцию и ее вызывать.
А функций несколько, надо с выводом значений - одна, надо счетчик - другая. Тогда оптимизатор не так сильно будет код ломать.
...
Рейтинг: 0 / 0
26.01.2021, 14:43
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40039025
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давайте уже подумаем над API использования этого софта.

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

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

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

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


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

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

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


Обычно результаты генерации не являются финальными результатами а как-то там еще обрабатываются.
Их не надо забирать, а надо обрабатывать по мере генерации.

Я думаю о дизайне самой упаковки. Тоесть если вы создали некий модуль (библиотеку) которая генерит
сочетания и выкладываете ее на github или еще куда-то не в виде исходного кода а как бинарник (.dll/.o) + .h
(как это принято в С++) то нужно подумать о том как ее будут использовать.

Один вариант - итератор как сделал Анатолий, размотав стек.

Я думаю над другими вариантами чтобы сохранив "рекурсивную природу" алгоритма сделать тем не менее
возможность удобно его использовать не ломая а используя то что уже разработано.
...
Рейтинг: 0 / 0
26.01.2021, 16:41
| Ответить | Цитировать | Написать  
25 сообщений из 174, страница 3 из 7
  3  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Генерация сочетаний из N по K
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=40038758&tid=1339689]:
 0ms
get settings:
 11ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 64ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 70ms
get tp. blocked users:
 2ms
others: 250ms
total:  435ms
созд. / загр.: 435ms
x
x
Закрыть


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