Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Получить все комбинации строк / 17 сообщений из 17, страница 1 из 1
28.06.2018, 16:20
    #39667245
Est_vopros
Est_vopros
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Добрый день!
Есть такая задачка:
Дано: таблица из одной колонки:
SABC
Требуется получить все комбинации:
NS1A2B3C4A4B5A5C6B6C7A7B7C
На чистом SQL 10-12 версий Oracle
На SQL + PL/SQL
Поделитесь, пожалуйста, если есть опыт решения подобных задачек на других инструментах. Есть подозрение, что для большого количества строк,исходных значений (50 и более) ни SQL ни SQL+PL/SQL не будут эффективны
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 16:52
    #39667266
Elic
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Est_voprosЕсть подозрение, что для большого количества строк,исходных значений (50 и более)Ты можешь себе представить мощность 2 50 ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 18:21
    #39667322
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
ElicEst_voprosЕсть подозрение, что для большого количества строк,исходных значений (50 и более)мощность 2 50 ?
Мелко мыслишь (c) Elic.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 19:28
    #39667343
Est_vopros
Est_vopros
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Elic представить мощность 2 50 ?
Нет ничего невозможного. Будет усложнение задачи, когда надо будет построить очередную комбинацию, проверить её по некоторым условиям, и только в случае невыполнения условий перейти к следующей комбинации. Согласен, что зря написал сразу про степень 50 не уточнив подход.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 19:41
    #39667347
d7i
d7i
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Число сочетаний из n-элементов по m-мест:
A=n!/(n-m)!
Вот и подсчитайте: K(3)=A(n=3; m=1)+A(n=3; m=2)+A(n=3; m=3)

Для n=50 будет много, но не 2 в степени 50...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 19:44
    #39667350
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Est_voprosзря написал сразу про степень 50 не уточнив подход.
Дык уточняйте.
А то какбэ Elic против обыкновения немножко оптимистичен (не учел желаемую форму представления)
 
Код: plsql
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.
  with n(v) as (select level+1 from dual connect by level <60)
select v "Число элементов"
     , to_char(power(2,v),'fm999G999G999G999G999G999G999G999G999G999') "Оценка Elic"
     , to_char(v/2*power(2,v),'fm999G999G999G999G999G999G999G999G999G999') "Реальность"
     , round((power(2,v))/(v/2*power(2,v)),2) "Отношение Elic к Реальность :)"
  from n
 where v<5 or mod(v,5)=0
;

Число элементов Оценка Elic                              Реальность                               Отношение Elic к Реальность :)
--------------- ---------------------------------------- ---------------------------------------- ------------------------------
              2 4                                        4                                                                     1
              3 8                                        12                                                                 0,67
              4 16                                       32                                                                  0,5
              5 32                                       80                                                                  0,4
             10 1 024                                    5 120                                                               0,2
             15 32 768                                   245 760                                                            0,13
             20 1 048 576                                10 485 760                                                          0,1
             25 33 554 432                               419 430 400                                                        0,08
             30 1 073 741 824                            16 106 127 360                                                     0,07
             35 34 359 738 368                           601 295 421 440                                                    0,06
             40 1 099 511 627 776                        21 990 232 555 520                                                 0,05
             45 35 184 372 088 832                       791 648 371 998 720                                                0,04
             50 1 125 899 906 842 624                    28 147 497 671 065 600                                             0,04
             55 36 028 797 018 963 968                   990 791 918 021 509 120                                            0,04
             60 1 152 921 504 606 846 976                34 587 645 138 205 409 280                                         0,03
15 rows selected

SQL>


И это... оно точно для СУБД задача? Сделать-то не проблема, но процессоры под СУБД денег стоят...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 19:51
    #39667352
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
d7iЧисло сочетаний из n-элементов по m-мест:
A=n!/(n-m)!
Код: plaintext
n!/((n-m)!*m!)
, с Вашего позволения.
Далее, судя по примеру ТС, требуется сгенерировать число групп, составляющих сумму ряда, а она равна именно power(2,N), Elic в этом прав.
Но ТС дополнительно хочет каждое сочетание оформить группой строк , что дает общий множитель (n/2), или *25 при 50 элементах алфавита.
Как-то так...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 19:58
    #39667354
SY
SY
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
d7iДля n=50 будет много, но не 2 в степени 50...

А что комбинаторику в школах уже не изучaют? И про факториалы тоже не слышал? n!/(n - k)! когда k = n очень упрощается. Ну и сравни 2**50 c 50!

SY.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 20:07
    #39667355
d7i
d7i
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Даны натуральные числа N и K.
Рассмотрим множество чисел от 1 до N.
Требуется вывести все различные его подмножества мощности K, причём в лексикографическом порядке.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
bool next_combination (vector<int> & a, int n) {
	int k = (int)a.size();
	for (int i=k-1; i>=0; --i)
		if (a[i] < n-k+i+1) {
			++a[i];
			for (int j=i+1; j<k; ++j)
				a[j] = a[j-1]+1;
			return true;
		}
	return false;
}



Замените числа 1...N на буквы A...Z и получите нужную функцию.
Как её впихнуть в СУБД - это уже второй вопрос...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.06.2018, 22:27
    #39667412
SY
SY
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
d7iКак её впихнуть в СУБД - это уже второй вопрос...


Впихнуть не проблема

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
with data as (
              select  chr(ascii('A') + level - 1) str
                from  dual
                connect by level <= &&n
             ),
r(
  lvl,
  str
 ) as (
        select  1,
                str
          from  data
       union all
        select  r.lvl + 1,
                r.str || ',' || d.str
          from  r,
                data d
          where d.str> r.str
            and r.lvl <= &&n
      )
select  str
  from  r
/



Проблема в числе комбинаций. Число комбинаций от 1 до 7 из 7 и время:

Код: plsql
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.
SQL> set timing on
SQL> define n=7
SQL> with data as (
  2                select  chr(ascii('A') + level - 1) str
  3                  from  dual
  4                  connect by level <= &&n
  5               ),
  6  r(
  7    lvl,
  8    str
  9   ) as (
 10          select  1,
 11                  str
 12            from  data
 13         union all
 14          select  r.lvl + 1,
 15                  r.str || ',' || d.str
 16            from  r,
 17                  data d
 18            where d.str> r.str
 19              and r.lvl <= &&n
 20        )
 21  select  count(*)
 22    from  r
 23  /
old   4:                 connect by level <= &&n
new   4:                 connect by level <= 7
old  19:             and r.lvl <= &&n
new  19:             and r.lvl <= 7

  COUNT(*)
----------
    458968

Elapsed: 00:00:02.87
SQL>




А вот окончания от 1 до 8 из 8 я не дождался.

SY.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2018, 00:53
    #39667441
dbms_photoshop
dbms_photoshop
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
SYА вот окончания от 1 до 8 из 8 я не дождался.Во-первых неправильно. Во-вторых долго. В-третьих вы сами были в теме, где быстро.
21529870
По крайней мере комбинации для всего алвафита от A до Z на моем ноуте генерирует за секунды.
С русским, где на 7 букв больше будет уже проблематичнее, но тоже меньше часа ждать.
А вот с 50 элементами туго, да.

Est_voprosElic представить мощность 2 50 ?
Нет ничего невозможного. Будет усложнение задачи, когда надо будет построить очередную комбинацию, проверить её по некоторым условиям, и только в случае невыполнения условий перейти к следующей комбинации. Согласен, что зря написал сразу про степень 50 не уточнив подход.Есть дохрена чего невозможного. Только и практического смысла в невозможных хотелках [как правило] мало.
Для примера, и заодно, чтоб лучше осознавать скорость роста экспоненциальных последовательностей почитай притчу про шахматную доску и зерно .
Странная цель захламлять память огромным числом комбинаций вместо того, чтоб пре-генерировать их на лету (возможно пачками) по мере проверки.
Ну и главное, выбор SQL как инструмента наводит на мысли, чтоб все это баловство.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2018, 00:55
    #39667443
dbms_photoshop
dbms_photoshop
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
dbms_photoshopв теме, где быстро 6849388
Ссылки разучился давать...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2018, 02:26
    #39667452
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
SYd7iДля n=50 будет много, но не 2 в степени 50...

А что комбинаторику в школах уже не изучaют? И про факториалы тоже не слышал? n!/(n - k)! когда k = n очень упрощается. Ну и сравни 2**50 c 50!

SY.да тут даже комбинаторику вспоминать не надо... Достаточно представить комбинацию в двоичном виде: 1 - элемент выбран, 0 - не выбран, и итого - 50 бит.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2018, 08:06
    #39667469
-2-
-2-
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
with t as (select column_value s from table(ku$_vcnt('A', 'B', 'C')))
select r, t2.column_value s
from (select rownum r, value(t0) x from table(powermultiset((select cast(collect(s) as ku$_vcnt) from t))) t0) t1, table(t1.x) t2;

         R S    
---------- -----
         1 A    
         2 B    
         3 A    
         3 B    
         4 C    
         5 A    
         5 C    
         6 B    
         6 C    
         7 A    
         7 B    
         7 C
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2018, 10:24
    #39667509
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
xtenderДостаточно представить комбинацию в двоичном виде: 1 - элемент выбран, 0 - не выбран, и итого - 50 бит.
...и размножить каждую комбинацию в "количество единиц в векторе" раз, что также приводит к ранее представленной формуле (N/2)*power(2,N).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2018, 12:13
    #39667571
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Утёнок, кстати, прекрасен.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2018, 18:18
    #39667715
Est_vopros
Est_vopros
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Получить все комбинации строк
Спасибо всем за проявленный интерес!
-2-
Большое спасибо!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Получить все комбинации строк / 17 сообщений из 17, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 492ms
Закрыть
start [/forum/topic.php?fid=52&mobile=1&tid=1883781]:
 0ms
get settings:
 8ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 176ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 56ms
get tp. blocked users:
 1ms
others: 218ms
total:  492ms
x
x
Закрыть


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