ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Генерация сочетаний из N по K
25 сообщений из 174, страница 6 из 7
  6  все
Генерация сочетаний из N по K
    #40040112
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Из любопытства вопрос, удельную скорость есть смысл сопоставить? К примеру кол-во на 1 ГГц процессора или ядра, на 1 ГБ памяти... Различия в операционках за кадром.
...
Рейтинг: 0 / 0
30.01.2021, 15:52
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040121
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, уже лучше.

Код: 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.
program perm_k_n;

uses
  SysUtils;

procedure ShowCombinationDesc(p: pIntegerArray; len: integer);
var
  s: AnsiString;
  i: integer;
begin;
  for i:=0 to len-1 do s:=s+AnsiChar(Ord('0')+p[i]);
  WriteLn(s);
  end;

function GenerateCombinationDesc(p: pIntegerArray; n, k: integer): integer;
var
  i: integer;
  Result: integer;
begin;
  Result:=0;
  i:=k;
  dec(i);
  while true do begin;
    while i>0 do begin;
      dec(n);
      p[i]:=n;
      dec(i);
      end;
    repeat;
      dec(n);
      p[0]:=n;
      inc(Result);                  //подсчет сочетаний
      //ShowCombinationDesc(p, k);  //обработка очередного сочетания
      until n<=0;
    repeat;
      inc(i); if i>=k then exit;
      n:=p[i];
      until i<n;
  end;
end;

var
  c: array of integer;
  p: pointer;           
  n, k, cnt: integer;
begin;
  n:=100; k:=6;
  SetLength(c, k);
  p:=@c[0];
  cnt:=GenerateCombinationDesc(p, n, k);
  WriteLn(cnt);
  ReadLn;
end.



Остались ошибки типизации.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
Hint: Start of reading config file /etc/fpc.cfg
Hint: End of reading config file /etc/fpc.cfg
Free Pascal Compiler version 3.0.4+dfsg-23 [2019/11/25] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling perm-k-n.lpr
perm-k-n.lpr(11,46) Error: Operator is not overloaded: "Byte" + "IntegerArray"
perm-k-n.lpr(26,13) Error: Incompatible types: got "SmallInt" expected "IntegerArray"
perm-k-n.lpr(31,13) Error: Incompatible types: got "SmallInt" expected "IntegerArray"
perm-k-n.lpr(37,11) Error: Incompatible types: got "IntegerArray" expected "SmallInt"
perm-k-n.lpr(53,4) Fatal: There were 4 errors compiling module, stopping
Fatal: Compilation aborted
Error: /usr/bin/ppcx64 returned an error exitcode
...
Рейтинг: 0 / 0
30.01.2021, 16:35
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040128
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98
Из любопытства вопрос, удельную скорость есть смысл сопоставить? К примеру кол-во на 1 ГГц процессора или ядра, на 1 ГБ памяти... Различия в операционках за кадром.


количество тактов на сочетание сильно зависит от количества элементов в сочетании, у меня так:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
из 180 по 5: 1488847536 за 547 мсек
1,32 тактов

из 100 по 6: 1192052400 за 453 мсек
1,37 тактов

из 64 по 7: 621216192 за 234 мсек
1,36 тактов

из 32 по 16: 601080390 за 609 мсек
3,65 тактов

из 36 по 24: 1251677700 за 2156 мсек
6,20 тактов
...
Рейтинг: 0 / 0
30.01.2021, 17:04
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040130
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

по-видимому нужно убрать вольности при работе с указателем
 
Код: 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.
program perm_k_n;

uses
  SysUtils;

procedure ShowCombinationDesc(p: pIntegerArray; len: integer);
var
  s: AnsiString;
  i: integer;
begin;
  for i:=0 to len-1 do s:=s+AnsiChar(Ord('0')+byte(p^[i]));
  WriteLn(s);
  end;

function GenerateCombinationDesc(p: pIntegerArray; n, k: integer): integer;
var
  i: integer;
begin;
  Result:=0;
  i:=k;
  dec(i);
  while true do begin;
    while i>0 do begin;
      dec(n);
      p^[i]:=n;
      dec(i);
      end;
    repeat;
      dec(n);
      p^[0]:=n;
      inc(Result);                  //подсчет сочетаний
      //ShowCombinationDesc(p, k);  //обработка очередного сочетания
      until n<=0;
    repeat;
      inc(i); if i>=k then exit;
      n:=p^[i];
      until i<n;
    end;
  end;

var
  c: array of integer;
  p: pointer;
  n, k, cnt: integer;
begin;
  n:=100; k:=6;
  SetLength(c, k);
  p:=@c[0];
  cnt:=GenerateCombinationDesc(p, n, k);
  WriteLn(cnt);
  ReadLn;
end.

...
Рейтинг: 0 / 0
30.01.2021, 17:16
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040131
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
А прога знает, что (37 по 24) == (37 по 13) ?
...
Рейтинг: 0 / 0
30.01.2021, 17:18
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040132
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98
А прога знает, что (37 по 24) == (37 по 13) ?


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

Код: sql
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.
program perm_k_n;

uses
  SysUtils;

procedure ShowCombinationDesc(p: pIntegerArray; len: integer);
var
  s: AnsiString;
  i: integer;
begin;
  for i:=0 to len-1 do s := s + AnsiChar(Ord('0') + byte(p^[i]));
  WriteLn(s);
end;

function GenerateCombinationDesc(p: pIntegerArray; n, k: integer): integer;
var
  i: integer;
  Result: Integer;
begin;
  Result:=0;
  i:=k;
  dec(i);
  while true do begin;
    while i>0 do begin;
      dec(n);
      p^[i]:=n;
      dec(i);
    end;
    repeat;
      dec(n);
      p^[0]:=n;
      inc(Result);                  //подсчет сочетаний
      ShowCombinationDesc(p, k);  //обработка очередного сочетания
    until n<=0;
    repeat;
      inc(i); if i>=k then exit;
      n:=p^[i];
    until i<n;
  end;
end;

var
  c: array of integer;
  p: pointer;
  n, k, cnt: integer;
begin;
  n:=6; k:=5;
  SetLength(c, k);
  p:=@c[0];
  cnt:=GenerateCombinationDesc(p, n, k);
  WriteLn(cnt);
end.



Отчот для C(5,6)
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
sharahov$ ./perm-k-n.exe 
12345
02345
01345
01245
01235
01234
-20104
...
Рейтинг: 0 / 0
30.01.2021, 18:41
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040150
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
надо присвоить результат значению функции
Код: 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.
function GenerateCombinationDesc(p: pIntegerArray; n, k: integer): integer;
var
  i: integer;
  Result: Integer;
label
  Done;
begin;
  Result:=0;
  i:=k;
  dec(i);
  while true do begin;
    while i>0 do begin;
      dec(n);
      p^[i]:=n;
      dec(i);
    end;
    repeat;
      dec(n);
      p^[0]:=n;
      inc(Result);                  //подсчет сочетаний
      ShowCombinationDesc(p, k);  //обработка очередного сочетания
    until n<=0;
    repeat;
      inc(i); if i>=k then goto Done;
      n:=p^[i];
    until i<n;
  end;
Done:
  GenerateCombinationDesc:=Result;
end;
...
Рейтинг: 0 / 0
30.01.2021, 18:51
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040164
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, уже работает но счетчик где-то циклически переполняется .

При

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
var
  c: array of integer;
  p: pointer;
  n, k, cnt: integer;
begin;
  n:=200; k:=2;
  SetLength(c, k);
  p:=@c[0];
  cnt:=GenerateCombinationDesc(p, n, k);
  WriteLn(cnt);
end.



Код: sql
1.
19900



При
Код: sql
1.
n:=400; k:=2;



Результат
Код: sql
1.
14264



А при n=600, результат -16908 (отрицательный)

А так по сорости быстро. Да. Очень быстро. Но надо фиксить.
...
Рейтинг: 0 / 0
30.01.2021, 20:54
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040165
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
Aleksandr Sharahov, уже работает но счетчик где-то циклически переполняется .
А при n=600, результат -16908 (отрицательный)


А k какое? Может, результат укладывается не укладывается в 32-битный integer?

попробуй заменить его на int32 или longint

пишут есть еще delphi mode: https://wiki.freepascal.org/Integer
...
Рейтинг: 0 / 0
30.01.2021, 21:05
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040204
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, если переключать в Delphi mode ({$mode DelphiUnicode}) то
компилляция останавливается. Еще новые ошибки выдает. Видимо уровни строгости выше.

Вобщем заменил Integer у которого разрядная сетка плавает (16-32 бит) на более строгий Int32
и пересобрал.

Вот последняя версия. Работает быстро. 2 из 10 000 выдает за милисекунды. Точно померять
не могу т.к. не знаю функций точных часов.

Вот последнний исходник.

 
Код: 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.
program perm_k_n;

uses
  SysUtils;

procedure ShowCombinationDesc(p: pIntegerArray; len: Int32);
var
  s: AnsiString;
  i: Int32;
begin;
  for i:=0 to len-1 do s := s + AnsiChar(Ord('0') + byte(p^[i]));
  WriteLn(s);
end;

function GenerateCombinationDesc(p: pIntegerArray; n, k: Int32): Int32;
var
  i: Int32;
  Result: Int32;
label
Done;
begin;
  Result:=0;
  i:=k;
  dec(i);
  while true do begin;
    while i>0 do begin;
      dec(n);
      p^[i]:=n;
      dec(i);
    end;
    repeat;
      dec(n);
      p^[0]:=n;
      inc(Result);                  //подсчет сочетаний
      //ShowCombinationDesc(p, k);  //обработка очередного сочетания
    until n<=0;
    repeat;
      inc(i); if i>=k then goto Done;
      n:=p^[i];
    until i<n;
  end;
  Done:
  GenerateCombinationDesc:=Result;
end;

var
  c: array of Int32;
  p: pointer;
  n, k, cnt: Int32;
begin;
  n:=10000; k:=2;
  SetLength(c, k);
  p:=@c[0];
  cnt:=GenerateCombinationDesc(p, n, k);
  WriteLn(cnt);
end.


...
Рейтинг: 0 / 0
31.01.2021, 02:09
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040220
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
exp98
А прога знает, что (37 по 24) == (37 по 13) ?

ИМХО это ничем не поможет. Сочетания по 13 думаю чуть быстрее будут генериться, но если начать их преобразовывать в сочетания по 24, то само преобразование займет больше времени чем мы сэкономили.
Все алгоритмы выше построены на получении из текущего состояния следующее, т.е. в среднем меняется несколько разрядов, а тут придется все обрабатывать каждый раз.
...
Рейтинг: 0 / 0
31.01.2021, 09:05
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040224
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

также имеет смысл заменить pIntegerArray на PInt32Array
и после uses добавить определения своих массивов:
Код: pascal
1.
2.
3.
type
  Int32Array  = array[0..$effffff] of Int32;
  PInt32Array = ^Int32Array;
...
Рейтинг: 0 / 0
31.01.2021, 11:11
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040311
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Dima T, а ты сравни у него близкие значения
авториз 32 по 16: 601080390 за 609 мсек
3,65 тактов

из 36 по 24: 1251677700 за 2156 мсек
6,20 тактов Разница в 2 раза. По проге посмотреть (может ошибаюсь), цикл в цикле, затраты n*k.
Считаем для k=n-k, а выход только преобразуем в к=к. Я так подумал. Особенно когда (1000, 800) против (1000, 200)
Нешто это съест економию? А так надо писать памятку по применению. Чтоб прогер перед вызовом и после сам по желанию преобразовывал туда-сюда.
...
Рейтинг: 0 / 0
31.01.2021, 20:18
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040318
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98
Dima T, а ты сравни у него близкие значения
авториз 32 по 16: 601080390 за 609 мсек
3,65 тактов

из 36 по 24: 1251677700 за 2156 мсек
6,20 тактов
Разница в 2 раза. По проге посмотреть (может ошибаюсь), цикл в цикле, затраты n*k.
Считаем для k=n-k, а выход только преобразуем в к=к. Я так подумал. Особенно когда (1000, 800) против (1000, 200)
Нешто это съест економию? А так надо писать памятку по применению. Чтоб прогер перед вызовом и после сам по желанию преобразовывал туда-сюда.

не все прогеры даже станут преобразовывать,
некоторые могут додуматься вместо элементов, вошедших в сочетание,
работать с невошедшими элементами
...
Рейтинг: 0 / 0
31.01.2021, 20:46
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040485
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
exp98
Dima T, а ты сравни у него близкие значения
авториз 32 по 16: 601080390 за 609 мсек
3,65 тактов

из 36 по 24: 1251677700 за 2156 мсек
6,20 тактов
Разница в 2 раза. По проге посмотреть (может ошибаюсь), цикл в цикле, затраты n*k.
Считаем для k=n-k, а выход только преобразуем в к=к. Я так подумал. Особенно когда (1000, 800) против (1000, 200)
Нешто это съест економию? А так надо писать памятку по применению. Чтоб прогер перед вызовом и после сам по желанию преобразовывал туда-сюда.
Это не близкие, надо считать сколько разрядов было задействовано для получение следующего значения. Например С(3,6)
ЗначениеРазрядов1 2 3 41 2 3 511 2 3 611 2 4 521 2 4 621 2 5 621 3 4 531 3 4 611 3 5 62...
Поменять может потребоваться от 1 до k разрядов. Назовем проверку разряда элементарной операцией.
Уже видно что в среднем будет менее k/2 элементарных операций.

Для преобразования от k к n-k надо перебрать все n и выкинуть из них все что есть с исходной выборке. В один проход делается, но это примерно n+k элементарных операций, т.е. все равно это будет дольше чем (n-k)/2. Как-то так.
...
Рейтинг: 0 / 0
01.02.2021, 13:58
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040487
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov

Код: pascal
1.
2.
type
  Int32Array  = array[0..$effffff] of Int32;


Саша а что эта форма объявления массива означает? Бесконечный массив? Или до effffff включительно?
...
Рейтинг: 0 / 0
01.02.2021, 14:07
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040514
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
Aleksandr Sharahov

Код: pascal
1.
2.
type
  Int32Array  = array[0..$effffff] of Int32;


Саша а что эта форма объявления массива означает? Бесконечный массив? Или до effffff включительно?


Формально, это массив от 0 до максимального значения, которое позволяет компилятор (effffff).
Но это всего лишь определение типа, т.е. реально память не выделяется, мы здесь просто говорим,
что с так объявленной памятью хотим работать как с массивом целых максимальной длины,
т.е. после целого с индексом 0 может быть расположено еще сколько угодно целых.

Понятно, что такой огромный массив нам не нужен, вся фишка в следующем определении
Код: pascal
1.
PInt32Array = ^Int32Array;


Оно говорит, что указатель типа PInt32Array указывает на нулевой элемент массива целых чисел,
т.е. через такой указатель можно работать с памятью как со статическим массивом целых чисел.

Обычно для статических массивов компилятор Delphi строит более эффективный код, чем для динамических массивов.
Поэтому память мы выделяем динамически вызовом SetLength, а работаем с ней как со статическим массивом на стеке.
...
Рейтинг: 0 / 0
01.02.2021, 14:59
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040534
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Понятно.
...
Рейтинг: 0 / 0
01.02.2021, 15:29
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040548
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Aleksandr Sharahov
Формально, это массив от 0 до максимального значения, ........ как со статическим массивом на стеке.
Ты книги должен писать по дельфе.
...
Рейтинг: 0 / 0
01.02.2021, 15:48
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040551
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Aleksandr Sharahov
некоторые могут додуматься вместо элементов, вошедших в сочетание,
работать с невошедшими элементами
А можно, чтобы прога додумывалась до этого сама? Ну-у, чтобы это без больших усилий прогера. Или, если надо тупо гнать массу сочетаний, то выдавать сразу взаимодополняемыми парами сочетаний?
...
Рейтинг: 0 / 0
01.02.2021, 15:56
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040564
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98
Aleksandr Sharahov
некоторые могут додуматься вместо элементов, вошедших в сочетание,
работать с невошедшими элементами
А можно, чтобы прога додумывалась до этого сама? Ну-у, чтобы это без больших усилий прогера. Или, если надо тупо гнать массу сочетаний, то выдавать сразу взаимодополняемыми парами сочетаний?


Можно, но немного допрограммировать придется.

Способ 1.
Если n небольшое, например n<=32 (или 64), сочетание можно представить целым числом,
биты которого равны 1 - если элемент входит в сочетание, 0 - если не входит.
Остается на входе выбрать меньшее k, а на выходе инвертировать сочетание (xor -1)

Способ 2.
Сначала ответим на вопрос: зачем вообще в нашей программе понадобились сочетания?
Ведь это не конечный результат работы, надо потом с ними что-то делать.
Далее: как это что-то мы будем делать?
Скорее всего, перебирая в цикле элементы, *вошедшие* в сочетание.
И что мешает нам как программистам предусмотреть цикл для *невошедших* элементов?
...
Рейтинг: 0 / 0
01.02.2021, 16:17
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040601
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Спос1 понятно.
Спос2: Дима полагает, что ускорения не достичь.

Dima T
Для преобразования от k к n-k надо перебрать все n и выкинуть из них все что есть с исходной выборке. В один проход делается, но это примерно n+k элементарных операций,
Вот с этим я не согласен. Они ведь упорядочены. Сравнил удачно и передвинул указатель к след. (n + o(k)) Операций.
...
Рейтинг: 0 / 0
01.02.2021, 17:26
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040626
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
exp98
Dima T
Для преобразования от k к n-k надо перебрать все n и выкинуть из них все что есть с исходной выборке. В один проход делается, но это примерно n+k элементарных операций,
Вот с этим я не согласен. Они ведь упорядочены. Сравнил удачно и передвинул указатель к след. (n + o(k)) Операций.

Благодаря тому что упорядочены можно преобразовать в один проход, но надо пройтись по всем элементам обоих массивов (n+k), когда для получения следующего значения надо поработать с менее k/2 элементов, даже если k максимально (n-1), то это всего лишь (n-1)/2
...
Рейтинг: 0 / 0
01.02.2021, 18:36
| Ответить | Цитировать | Написать  
Генерация сочетаний из N по K
    #40040692
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98
Спос1 понятно.
Спос2: Дима полагает, что ускорения не достичь.

Dima T
Для преобразования от k к n-k надо перебрать все n и выкинуть из них все что есть с исходной выборке. В один проход делается, но это примерно n+k элементарных операций,
Вот с этим я не согласен. Они ведь упорядочены. Сравнил удачно и передвинул указатель к след. (n + o(k)) Операций.


Ответ на этот вопрос и ожидаемый, и удивительный.
Если коротко, Dima T прав. Удивительно, как сильно он прав )

Даже если реализовать второй способ по уму, и вообще не формировать новое сочетание,
а обрабатывать элементы "на лету", то все равно n лишних сравнений для каждого сочетания
вносят замедление, которое значительно перевешивает полученный при генерации выигрыш.

Проверку я проводил на том же примере 24 из 36.
Обработка сочетаний заключалась в вычислении общей суммы всех элементов сочетаний по модулю 2^32.
"Оптимизированный" вариант, который вычислял сумму элементов, не вошедших в сочетания 12 из 36,
оказался в 2 раза медленнее.

Вывод.
Выгоднее сразу генерировать сочетания, которые не требуется "переделывать" перед обработкой.
...
Рейтинг: 0 / 0
01.02.2021, 21:11
| Ответить | Цитировать | Написать  
25 сообщений из 174, страница 6 из 7
  6  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Генерация сочетаний из N по K
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=40040487&tid=1339689]:
 0ms
get settings:
 7ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 53ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 63ms
get tp. blocked users:
 1ms
others: 262ms
total:  420ms
созд. / загр.: 420ms
x
x
Закрыть


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