ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Получить все комбинации строк
17 сообщений из 17, страница 1 из 1
Получить все комбинации строк
    #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:20
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #39667266
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Elic
Участник
Est_voprosЕсть подозрение, что для большого количества строк,исходных значений (50 и более)Ты можешь себе представить мощность 2 50 ?
...
Рейтинг: 0 / 0
28.06.2018, 16:52
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #39667322
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
ElicEst_voprosЕсть подозрение, что для большого количества строк,исходных значений (50 и более)мощность 2 50 ?
Мелко мыслишь (c) Elic.
...
Рейтинг: 0 / 0
28.06.2018, 18:21
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #39667343
Est_vopros
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Est_vopros
Гость
Elic представить мощность 2 50 ?
Нет ничего невозможного. Будет усложнение задачи, когда надо будет построить очередную комбинацию, проверить её по некоторым условиям, и только в случае невыполнения условий перейти к следующей комбинации. Согласен, что зря написал сразу про степень 50 не уточнив подход.
...
Рейтинг: 0 / 0
28.06.2018, 19:28
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #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:41
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #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:44
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #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:51
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #39667354
Фотография SY
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SY
Участник
d7iДля n=50 будет много, но не 2 в степени 50...

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

SY.
...
Рейтинг: 0 / 0
28.06.2018, 19:58
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #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, 20:07
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #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
28.06.2018, 22:27
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #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:53
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #39667443
Фотография dbms_photoshop
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dbms_photoshop
Участник
dbms_photoshopв теме, где быстро 6849388
Ссылки разучился давать...
...
Рейтинг: 0 / 0
29.06.2018, 00:55
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #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, 02:26
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #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, 08:06
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #39667509
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
xtenderДостаточно представить комбинацию в двоичном виде: 1 - элемент выбран, 0 - не выбран, и итого - 50 бит.
...и размножить каждую комбинацию в "количество единиц в векторе" раз, что также приводит к ранее представленной формуле (N/2)*power(2,N).
...
Рейтинг: 0 / 0
29.06.2018, 10:24
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #39667571
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
Утёнок, кстати, прекрасен.
...
Рейтинг: 0 / 0
29.06.2018, 12:13
| Ответить | Цитировать | Написать  
Получить все комбинации строк
    #39667715
Est_vopros
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Est_vopros
Гость
Спасибо всем за проявленный интерес!
-2-
Большое спасибо!
...
Рейтинг: 0 / 0
29.06.2018, 18:18
| Ответить | Цитировать | Написать  
17 сообщений из 17, страница 1 из 1
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Получить все комбинации строк
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&fpage=109&tid=1883781]:
 0ms
get settings:
 11ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 34ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 33ms
get tp. blocked users:
 1ms
others: 269ms
total:  371ms
созд. / загр.: 371ms
x
x
Закрыть


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